Kth Smallest Element in a BST
Last Updated: March 29, 2026
Understanding the Problem
We have a binary search tree and need to find the kth smallest element in it. Since it's a BST, there's an implicit sorted order hiding in the tree structure. An in-order traversal (left, root, right) visits BST nodes in ascending order. So the kth node visited during an in-order traversal is our answer.
The real question is how efficiently we can get to that kth node. A naive approach would collect all values into a sorted list and pick the kth one. But we can do better by stopping the traversal as soon as we've visited k nodes, without needing to process the entire tree.
Key Constraints:
1 <= k <= n <= 10^4→ k is always valid (never larger than the number of nodes). We don't need to handle the case where k exceeds the tree size. With n up to 10,000, even O(n) approaches are fine.0 <= Node.val <= 10^4→ Non-negative integer values. No overflow concerns.- The tree is guaranteed to be a valid BST, so in-order traversal will always yield sorted values.
Approach 1: In-Order Traversal (Store All Values)
Intuition
The most straightforward approach exploits the fundamental property of a BST: an in-order traversal produces values in ascending order. If we collect all values into a list via in-order traversal, the kth smallest is simply the element at index k-1.
This is the approach most people think of first. It's correct and easy to implement, but it does more work than necessary because it traverses the entire tree even if k is 1.
Algorithm
- Perform a complete in-order traversal of the BST.
- Store each node's value in a list as you visit it.
- Return the element at index
k - 1from the list.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node in the tree exactly once during the in-order traversal, regardless of what k is.
- Space Complexity: O(n). We store all n node values in a list. On top of that, the recursion stack uses O(h) space where h is the tree height.
This works correctly but always traverses the entire tree and stores all values. What if we stopped the moment we found the kth element instead of collecting everything first?
Approach 2: Recursive In-Order with Early Stopping
Intuition
We know in-order traversal visits BST nodes in ascending order. Instead of collecting all values and then picking the kth one, we can count as we traverse and stop the moment our count reaches k.
The idea is simple: maintain a counter that increments each time we "visit" a node (the middle step of in-order). When the counter hits k, we've found our answer. The trick in the recursive version is propagating this early termination. We use class-level variables (or pass state by reference) to track the count and result across recursive calls.
The BST property guarantees that an in-order traversal visits nodes in ascending order. By counting each visit, the kth node we visit is exactly the kth smallest. The early return stops unnecessary processing, but in the recursive version, the "return" only exits the current call frame. The parent calls still need to check whether the result was found before recursing into the right subtree.
Algorithm
- Initialize a counter at 0 and a variable to hold the result.
- Start an in-order traversal from the root.
- Recurse into the left subtree.
- Increment the counter. If it equals k, record the current node's value as the result and stop further processing.
- If the result hasn't been found yet, recurse into the right subtree.
Example Walkthrough
Code
- Time Complexity: O(h + k). We traverse down to the leftmost node (h steps in the worst case), then visit k nodes in order. For a balanced BST, this is O(log n + k).
- Space Complexity: O(h). The recursion stack depth is proportional to the tree height. O(log n) for a balanced tree, O(n) for a skewed tree.
The recursive early-stop works well, but the termination isn't perfectly clean since returning only exits the current call frame. What if we used an iterative approach with an explicit stack so we could return the answer immediately?
Approach 3: Iterative In-Order Traversal with Stack
Intuition
An iterative in-order traversal gives us the same ascending visit order as the recursive version, but with one significant advantage: we have full control over when to stop. The moment we've visited the kth node, we return immediately. No call stack to unwind, no extra recursive calls.
The iterative approach uses an explicit stack. We push nodes as we go left, then pop a node, "visit" it (decrement k), and if k reaches 0, that node's value is our answer. Otherwise, move to its right child and repeat the process.
The iterative approach simulates exactly what the call stack does during recursive in-order traversal. Each time we push nodes going left, we're mimicking the recursive descent into left subtrees. When we pop, we're at the "visit" step. Moving to the right child is the equivalent of the recursive call on the right subtree. The critical advantage is that when k reaches 0, we return instantly from the function. No stack unwinding, no wasted processing.
Algorithm
- Initialize an empty stack and set the current node to root.
- While the stack is non-empty or the current node is not null:
- Push the current node onto the stack and move to its left child. Keep going until you reach null.
- Pop the top node from the stack. Decrement k.
- If k is 0, return this node's value.
- Otherwise, set the current node to the popped node's right child.
- Continue until k reaches 0.
Example Walkthrough
Code
- Time Complexity: O(h + k). We first traverse down to the leftmost node (at most h steps), then pop k nodes from the stack. For a balanced BST, this is O(log n + k). In the worst case (completely skewed tree with k = n), this is O(n).
- Space Complexity: O(h). The stack holds at most h nodes at any point, where h is the height of the tree. For a balanced BST, O(log n). For a completely skewed tree, O(n).