Kth Smallest Element in a BST

Kth Smallest Element in a BST looks like a tree problem, but it is really an ordering problem in disguise. The trick is knowing one fact about binary search trees: an in-order traversal hands you the values already sorted.

The slow way first

The brute-force approach: traverse the whole tree, collect every value into a list, sort the list, and return list[k - 1]. That works, but it visits all n nodes and then sorts — O(n log n) time and O(n) space, even when k is tiny.

The question to ask: do I actually need every value? No — I only need the first k in sorted order. If I can produce values in sorted order one at a time, I can stop the moment I have produced k of them.

The idea: in-order visits a BST in sorted order

In a BST, every value in the left subtree is smaller than the node, and every value in the right subtree is larger. So an in-order traversal — visit left subtree, then the node, then right subtree — emits values from smallest to largest. The k-th value it emits is the k-th smallest.

To stop early we run the traversal iteratively with an explicit stack: dive left as far as we can (pushing every node), pop the deepest node (the next smallest), count it, and only then turn to its right subtree.

The key insight: we never need to visit the whole tree. The instant count reaches k, the node we just popped is the answer and we return.

Walk through it

Step through the animation. We push 5, 3, 2, 1 going left, then pop them back. Popping 1 makes count 1; popping 2 makes count 2 and queues its right child 4; popping 4 makes count 3 == k, so we return 4 and stop — nodes 5 and 6 are never even touched.

Pseudocode

stack = empty, count = 0, node = root
while node is not null OR stack is not empty:
    while node is not null:        # go as far left as possible
        push node, node = node.left
    node = pop stack               # the next-smallest unvisited node
    count = count + 1
    if count == k:
        return node.value          # found it, stop early
    node = node.right              # now explore its right subtree

The Python solution

def kth_smallest(root, k):
    stack, count = [], 0
    node = root
    while node or stack:
        while node:          # go as far left as possible
            stack.append(node)
            node = node.left
        node = stack.pop()   # smallest unvisited node
        count += 1
        if count == k:
            return node.val
        node = node.right    # then explore the right subtree
    return -1

• The inner while node: loop walks down the left spine, stacking nodes so we remember where to return.
• stack.pop() always gives the smallest unvisited node, because the left-most node is on top.
• count += 1 then if count == k is the early stop — we return the moment we have emitted k values.
• node = node.right is what makes this in-order: after a node, we explore its right subtree before backing up further.

Complexity

We descend the height h of the tree to reach the smallest value, then pop k times — O(h + k), far less than the whole tree when k is small. Space is O(h) for the stack (the left spine on it at most).

When this pattern shows up

Practice