# Kth Smallest Element in a BST

- **Canonical ID**: `kth-smallest-element-in-a-bst`
- **Canonical URL**: https://dsacheatsheet.com/problems/kth-smallest-element-in-a-bst
- **Difficulty**: medium
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

## 1. Core Invariant / The Trick

Iterative inorder traversal using an explicit stack stops immediately on the `k`-th pop—visiting only `O(H + k)` nodes instead of traversing the entire tree.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(H + k)`
- **Space Complexity**: `O(H)`
- **Proof**: BST inorder yields elements in sorted ascending order; descending down the left spine pushes O(H) nodes and the first k pops return the k-th smallest.

## 3. Minimal Idiomatic Code

### Python
```python
def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack, curr = [], root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right
    return -1
```

### TypeScript
```typescript
export function kthSmallest(root: TreeNode | null, k: number): number {
  const stack: TreeNode[] = [];
  let curr = root;
  while (stack.length > 0 || curr) {
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop()!;
    if (--k === 0) return curr.val;
    curr = curr.right;
  }
  return -1;
}
```

### C++
```cpp
int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    while (root || !st.empty()) {
        while (root) { st.push(root); root = root->left; }
        root = st.top(); st.pop();
        if (--k == 0) return root->val;
        root = root->right;
    }
    return -1;
}
```

### Java
```java
int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> st = new ArrayDeque<>();
    while (root != null || !st.isEmpty()) {
        while (root != null) { st.push(root); root = root.left; }
        root = st.pop();
        if (--k == 0) return root.val;
        root = root.right;
    }
    return -1;
}
```

### Go
```go
func kthSmallest(root *TreeNode, k int) int {
    var st []*TreeNode
    for root != nil || len(st) > 0 {
        for root != nil { st = append(st, root); root = root.Left }
        root = st[len(st)-1]; st = st[:len(st)-1]
        k--
        if k == 0 { return root.Val }
        root = root.Right
    }
    return -1
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Collecting all N elements into an array ignores early exit and uses unnecessary O(N) memory.

### Follow-ups
- Frequent inserts/deletes + k-th queries: augment each BST node with `leftSubtreeSize` for O(H) order-statistic queries.