Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
An in-order traversal of a BST visits values in sorted ascending order, so the k-th node visited is the k-th smallest. The interview-grade answer is an iterative in-order walk using an explicit stack: push left spine, pop a node (count it), and when the count hits k, return that node — stopping early without traversing the rest. O(h + k) time, O(h) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you know in-order traversal of a BST produces sorted order, and whether you can implement it iteratively to stop early at the k-th element instead of materializing all values.
Where candidates slip
Collecting every value into a list and indexing [k-1] (O(n) time and space) when an early-terminating in-order walk is O(h + k), or doing reverse in-order and getting k-th largest by accident.
How to stand out
Give the iterative in-order with early stop, state the O(h + k) cost, and mention the follow-up: if the BST is modified often, augment nodes with subtree sizes for O(h) per query.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewk-th smallest in BSTStop early after k elements?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Full In-Order into a List
1Hint 1Explore hintHide hint
What order does an in-order traversal of a BST produce the values in?
2Hint 2Explore hintHide hint
Collect every value with a recursive in-order traversal into a list — it comes out sorted.
3Hint 3Explore hintHide hint
The answer is the element at index k - 1 of that sorted list.
A · Core idea
The simplest correct solution leans entirely on the BST in-order property: traverse left, visit node, traverse right, appending each value. The resulting list is sorted ascending, so the k-th smallest sits at index k - 1.
Why in-order is sorted on a BST. For any node, every value in its left subtree is smaller and every value in its right subtree is larger. Visiting left-subtree-then-node-then-right-subtree therefore emits values in non-decreasing order by construction — a proof you should be ready to state.
Why we don't ship this. It always touches all n nodes and stores all n values even when k is tiny (say k = 1). That's wasteful: we could stop as soon as we've seen k elements. It also uses O(n) extra memory for the list. Mention it as the baseline, then optimize to an early-terminating iterative walk.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [5,3,6,2,4,null,null,1], k = 3in-order
visit left spine then nodes
values = [1,2,3,4,5,6]3C · Code with teaching comments
Reference implementation preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Recognizing 'in-order traversal of a BST = sorted order' is the entire battle. Everything after is about not doing more work than necessary: stop at k, and avoid storing the whole list.
ComplexityO(n) time, O(n) space — We visit all n nodes and store all n values regardless of k → O(n) time and O(n) space (plus O(h) recursion stack).
E · Edge cases and pitfalls3Indexing values[k] instead of values[k-1] — off-by-one from 1-indexing.Explore edge casesHide edge cases
Pitfalls
- Indexing values[k] instead of values[k-1] — off-by-one from 1-indexing.
- Storing all n values when k could be small — wasteful.
- Pre-order or post-order instead of in-order — those aren't sorted.
Approach 2 of 2 · Optimal
Iterative In-Order with Early Stop (Optimal)
1Hint 1Explore hintHide hint
You don't need every value — only the k-th. How can you walk in-order but stop as soon as you've counted k nodes?
2Hint 2Explore hintHide hint
Simulate the recursion with an explicit stack: push the whole left spine, then pop to 'visit' the smallest remaining node.
3Hint 3Explore hintHide hint
Each pop yields the next value in sorted order. Decrement k on each pop; when k hits 0, that popped node is the answer. After popping, move to the node's right child and repeat.
A · Core idea
We make the in-order traversal explicit so we control exactly when to stop. The stack holds the chain of ancestors we still owe a visit, mirroring what recursion would keep on the call stack.
The push-left-spine, pop, go-right loop. Starting at the root, we push nodes while going left until there's no left child — the top of the stack is now the smallest unvisited value. We pop it (this is the in-order 'visit'), count it, and then move to its right child, where we again push its entire left spine. Repeating this yields nodes in sorted ascending order, one pop at a time.
Why this lets us stop early. Because each pop emits the next-smallest value, the k-th pop is the k-th smallest. We decrement k on every pop and return as soon as k == 0, so we never touch the part of the tree beyond the k-th element. For small k on a tall tree, that's dramatically less work than the full traversal.
Why the stack depth is O(h). At any moment the stack contains a single descending-left path from some node, which is at most the tree height. So extra memory is O(h), not O(n) — another win over the list approach.
Mapping to recursion. This is precisely the recursive in-order (left, visit, right) with the call stack made manual. Manual control is what enables the early return; a naive recursion would need a flag or exception to break out cleanly.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [5,3,6,2,4,null,null,1], k = 3Interactive diagram
In-order order on the example BST
push left spinePopping in in-order yields 1,2,3,4,5,6; the 3rd pop (node 3) is the answer.
3C · Code with teaching comments
D · Why it works and complexityO(h + k) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
An explicit stack turns 'traverse the whole tree' into 'generate sorted values lazily, one pop at a time'. That lazy generator view is exactly the BST Iterator pattern (LeetCode 173) — next() is one iteration of this loop.
ComplexityO(h + k) time, O(h) space — We descend the left spine (up to h pushes) and then pop k nodes, each push/pop O(1) → O(h + k) time. The stack holds at most one root-to-leaf path → O(h) space.
E · Edge cases and pitfalls6k = 1 — We push the left spine, pop the deepest-left node first, k → 0 immediately → the minimum. Only O(h) work.Explore edge casesHide edge cases
Edge cases handled
k = 1We push the left spine, pop the deepest-left node first, k → 0 immediately → the minimum. Only O(h) work.k = n (largest)We pop every node; the last is the maximum. Full O(n) traversal, which is unavoidable for the largest.Right-skewed tree (no left children)Stack never holds more than one node at a time; we pop root, go right, repeat — still correct, O(k) pops.
Pitfalls
- Forgetting to go to node.right after popping — you'd never advance past the left spine.
- Decrementing k in the wrong place or using k <= 0 vs k == 0 incorrectly.
- Using recursion without an early-exit mechanism, losing the O(h + k) advantage.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code preview// Definition for a binary tree node. // class TreeNode { // int val; // TreeNode left; // TreeNode right;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong traversal order
Only in-order (left, node, right) visits a BST's values in sorted order. Pre-order or post-order interleave subtrees and are not sorted, so counting to k gives the wrong element.
Explore the code comparisonHide the code comparison
Wrong traversal order
Only in-order (left, node, right) visits a BST's values in sorted order. Pre-order or post-order interleave subtrees and are not sorted, so counting to k gives the wrong element.
Don't write this
def preorder(node): # NOT sorted on a BST
if not node: return
values.append(node.val)
preorder(node.left)
preorder(node.right)Write this instead
def inorder(node): # sorted on a BST
if not node: return
inorder(node.left)
values.append(node.val)
inorder(node.right)2Not stopping early
Building the full sorted list is O(n) time and space even when k is small. An iterative in-order returns at the k-th pop in O(h + k) time and O(h) space.
Explore the code comparisonHide the code comparison
Not stopping early
Building the full sorted list is O(n) time and space even when k is small. An iterative in-order returns at the k-th pop in O(h + k) time and O(h) space.
Don't write this
List<Integer> all = new ArrayList<>();
inorder(root, all); // visits all n nodes
return all.get(k - 1);Write this instead
while (node != null || !stack.isEmpty()) {
while (node != null) { stack.push(node); node = node.left; }
node = stack.pop();
if (--k == 0) return node.val; // stop at k-th
node = node.right;
}Revise
Carry the pattern into the interview
Pattern to remember
In-order traversal of a BST (sorted order)
Code pattern to memorize
stack = []
node = root
while stack or node:
while node: # dive down the left spine
stack.append(node)
node = node.left
node = stack.pop() # smallest unvisited
k -= 1
if k == 0: return node.val
node = node.rightRules to remember
- 1In-order (left → node → right) on a BST yields sorted ascending order — that's the whole insight.
- 2Use an iterative stack so you can stop the moment the count reaches k; don't traverse the whole tree.
- 3Push the entire left spine before popping — the deepest-left node is the current smallest.
- 4Decrement k as you pop; return when k hits 0 (1-indexed k means k-th smallest).
- 5Time is O(h + k) — descend to the smallest (h) then pop k nodes — not O(n) if you stop early.
Use this pattern when
- Need the k-th smallest / largest in a **BST** (in-order gives sorted order)
- Need sorted output or order statistics from a BST without sorting separately
- Want to stop early after collecting k elements rather than scanning everything
- Validate-BST, range-sum, or 'closest value' problems that lean on in-order order
Choose another pattern when
- It's an unsorted array, not a BST → use a heap or Quickselect for k-th smallest
- k-th largest is wanted → reverse in-order (right → node → left) or use k = n − k + 1
- Many repeated k-th queries with updates → augment nodes with subtree counts for O(h) per query
- Tree isn't a BST → in-order won't be sorted; sort the values instead
Interview takeaway
The defining property of a BST is that in-order traversal emits values in sorted order. Once you internalize that, 'k-th smallest' becomes 'stop the in-order walk after k pops'. The iterative-stack template here is the same one used for Validate BST, BST Iterator, and Recover BST.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternIn-order traversal of a BST yields sorted order. Reach for it whenever you need order statistics, sorted output, or 'k-th' queries on a BST. The iterative-stack template with early termination is shared with BST Iterator, Validate BST, and Recover BST.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Binary Search Tree IteratorComing soonThe same iterative in-order, exposed as next()/hasNext() — each next() is one loop iteration.
- Validate Binary Search TreeIn-order must be strictly increasing — check each value against the previous one.
- Convert BST to Greater TreeComing soonReverse in-order (right, node, left) accumulating a running sum of larger values.
- Kth Largest Element in an ArrayComing soonNo BST structure — use a heap or Quickselect for k-th order statistic on an array.