We have a binary search tree and need to find the kth smallest element in it. A BST stores values in sorted order implicitly through its structure: every node's left subtree holds smaller values and its right subtree holds larger ones. An in-order traversal (left, root, right) walks the tree in ascending order, so the kth node visited during an in-order traversal is the answer.

The question is how efficiently we can reach that kth node. Collecting all values into a list and indexing into it works, but it processes the whole tree even when k is 1. Stopping as soon as we have visited k nodes avoids the wasted work.

Key Constraints:

Intuition

An in-order traversal of a BST produces values in ascending order. Collect those values into a list, and the kth smallest is the element at index k-1.

This is correct and easy to implement, but it always traverses the entire tree and stores every value, even when k is 1.

Algorithm

Example Walkthrough

Code

The next approach removes the list and stops the traversal as soon as the kth node is reached.

Intuition

Since in-order traversal visits BST nodes in ascending order, we can count nodes as we visit them rather than storing them. Maintain a counter that increments at the "visit" step (the middle step of in-order). When the counter reaches k, the current node holds the answer.

The complication is propagating the result out of recursion. A return only exits the current call frame, so the count and result are kept in shared state (class fields here, or parameters passed by reference) that every frame can read and write. The result is written exactly once, on the single visit where count == k. Parent frames keep running and may increment the counter past k, but since the equality check fires only once, the recorded answer is never overwritten. This version stops issuing new work down each branch but does not guarantee the full traversal halts immediately, which is the limitation the iterative version removes.

Algorithm

Example Walkthrough

Code

The recursive version writes the answer correctly but cannot guarantee it halts the moment the kth node is found. The iterative version with an explicit stack returns immediately on that node.

Intuition

An iterative in-order traversal produces the same ascending visit order as the recursive version, with one advantage: when the kth node is reached, the function returns directly out of the loop. No ancestor frames resume, so no node past the kth is ever visited.

The traversal uses an explicit stack. Push nodes while moving left, then pop a node, treat the pop as the visit (decrement k), and if k reaches 0, that node's value is the answer. Otherwise move to its right child and repeat.

The stack reproduces the recursive call stack step for step. Pushing nodes while going left mirrors the descent into left subtrees. A pop is the visit step. Moving to the right child stands in for the recursive call on the right subtree. Returning out of the loop on k == 0 is the part the recursion could not do cleanly.

Algorithm

Example Walkthrough

Code