Kth Smallest Element in a BST (LeetCode 230)

The problem

You get the root of a binary search tree and an integer k (1-indexed). Return the kth smallest value in the tree.

Input:  root = [5, 3, 6, 2, 4, null, null, 1], k = 3

            5
           / \
          3   6
         / \
        2   4
       /
      1

Output: 3

In sorted order the values are 1, 2, 3, 4, 5, 6, and the third one is 3.

How to think about it

Start with brute force. Collect every value into a list, sort it, and return values[k - 1]. That’s O(n log n) and O(n) memory. It works on any tree, which is the problem: it ignores the fact that this one is a BST.

The key insight: in-order traversal of a BST is already sorted. Visiting left subtree, then node, then right subtree yields values in increasing order. So you don’t need to sort. Walk in order and count; the kth node you visit is the answer. You can also stop the moment you reach it, without touching the rest of the tree.

Why iterative? Stopping early from deep inside a recursion is awkward (you need a counter outside and a way to unwind). With an explicit stack, “stop” is just return. The loop is the standard iterative in-order: push the whole left spine, pop one node (that’s the next smallest), then move to its right child and repeat.

Which pattern is this? Tree DFS (in-order) on a BST. The tell is “kth smallest” or “sorted order” plus “BST”. Any time a BST question mentions order, think in-order traversal.

Approach

1. Start with an empty stack and cur = root.
2. While cur is not empty, push it and go left. This reaches the smallest unvisited node.
3. Pop a node. It is the next value in sorted order, so decrease k.
4. If k hits 0, return that node’s value.
5. Otherwise set cur to the popped node’s right child and repeat from step 2.

Solution

def kth_smallest(root, k):
    st = []; cur = root
    while st or cur:
        while cur: st.append(cur); cur = cur.left            # dive down the left spine
        cur = st.pop(); k -= 1                               # next value in sorted order
        if k == 0: return cur.val
        cur = cur.right                                      # then its right subtree
# kth_smallest(tree[3,1,4,null,2], 1) -> 1

Dry run

On the example with k = 3:

k reaches 0 on node 3, so the answer is 3. Nodes 4, 5 and 6 are never popped.

Complexity

• Time: O(h + k). You first walk down up to h nodes to reach the minimum, then pop k nodes. In the worst case (k = n) that’s O(n).
• Space: O(h). The stack holds at most one root-to-leaf path: O(log n) balanced, O(n) skewed.

Edge cases and pitfalls

• k = 1 returns the minimum, the leftmost node.
• k = n returns the maximum; the code visits every node, which is fine.
• Off-by-one. k is 1-indexed. Decrementing before the check (as here) is correct; checking k == 1 before decrementing also works, but don’t mix the two.
• Follow-up: many queries on a changing tree. Store each node’s subtree size; then you can find the kth smallest in O(h) by comparing k with the left subtree’s size.

Related problems

• Validate Binary Search Tree (LeetCode 98): the in-order of a valid BST is strictly increasing.
• Kth Largest Element in an Array (LeetCode 215): the same “kth” question with no ordering, solved with a heap.
• Lowest Common Ancestor of a BST (LeetCode 235): another BST problem where the ordering does the work.