230. Kth Smallest Element in a BST

The trick to this one is a single fact about binary search trees that turns a “find the kth smallest” question into a counting problem. It’s a clean entry point into the binary tree traversal patterns, and once you see it you’ll stop reaching for sorting.

The problem

You’re given the root of a binary search tree and a number k, and you return the kth smallest value in the tree, counting from 1. (Full statement on LeetCode.)

For a tree holding {2, 3, 4, 5, 7}, k = 2 gives 3 — the second smallest.

Intuition: inorder walk yields sorted values

A BST has one property that does all the work here: every value in a node’s left subtree is smaller than the node, and everything in the right subtree is larger. If you visit left, then node, then right — an inorder traversal — you touch the values in ascending order. No sorting needed; the tree is already sorted, you just have to read it in the right order.

So finding the kth smallest collapses to: walk inorder, count nodes as you visit them, and stop the moment the counter hits k. That node’s value is the answer.

The nice part is you don’t have to walk the whole tree. Once you’ve counted k nodes, you’re done — everything to the right is larger and irrelevant. In the worst case (k = n, or a degenerate line of nodes) you still visit every node, but on average you bail early.

Solution

An iterative inorder with an explicit stack makes the early stop natural. You push your way down the left spine, then pop nodes off one at a time — each pop is the next value in sorted order.

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            // Dive to the smallest unvisited node, stacking the path.
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();          // next value in ascending order
            if (--k == 0) return node.val;  // kth node popped -> answer
            node = node.right;           // now explore the right subtree
        }
        return -1;  // unreachable given a valid k
    }
}

The recursive version is shorter but walks the same order — you’d keep a counter as a field and return once it reaches k. I prefer the stack here because stopping early is just a return inside the loop, with no shared mutable state to reason about.

Complexity

	Time	Space
Iterative inorder	$O(H + k)$	$O(H)$

You descend the left spine once ($O(H)$, where $H$ is the tree height) and then pop $k$ nodes, so time is $O(H + k)$ — bounded by $O(n)$ in the worst case. The stack holds at most one root-to-leaf path, so space is $O(H)$: $O(\log n)$ for a balanced tree, $O(n)$ for a skewed one.

In an interview

State the key fact first — “inorder traversal of a BST gives sorted order” — because that one line is what’s actually being tested. Then the code is just an inorder walk with a countdown. The trap is forgetting that the BST property is the whole point and reaching for a heap or a full sort; that works but throws away the structure you were handed.

The follow-up worth naming: if the tree is modified often and you query the kth smallest repeatedly, augment each node with the size of its subtree. Then you can navigate to the kth smallest in $O(H)$ per query without a fresh traversal, at the cost of maintaining counts on insert and delete.

This inorder idea also underpins Validate Binary Search Tree, where a sorted inorder sequence is exactly the validity check. For a different way of exploiting the BST ordering, see how the same left/right comparison guides Lowest Common Ancestor of a BST. Both live under the binary tree traversal patterns.

References

• LeetCode 230 — Kth Smallest Element in a BST