Kth Smallest Element in a BST: Inorder Traversal Counting

You are given the root of a binary search tree and an integer k. Return the kth smallest value in the tree (1-indexed).

This is LeetCode 230: Kth Smallest Element in a BST. The key insight is that an inorder traversal of a BST visits nodes in ascending sorted order. So finding the kth smallest element is the same as finding the kth node visited during an inorder traversal.

Example: for the BST [5, 3, 6, 2, 4] with k = 3, the inorder traversal visits 2, 3, 4, 5, 6. The 3rd smallest element is 4.

The approach

Since inorder traversal of a BST gives you sorted order, you just need to count how many nodes you have visited. The moment you reach the kth node, you have your answer.

The iterative approach with an explicit stack is ideal here because you can stop early. Once you have found the kth element, you return immediately without visiting the rest of the tree. A recursive approach would work too, but early termination is cleaner with a stack.

Here is the plan:

1. Use a stack and a pointer curr starting at the root.
2. Push nodes going left until there is no left child (this gets you to the smallest element).
3. Pop a node from the stack. Decrement k. If k reaches 0, this is your answer.
4. If k is not 0 yet, move to the right child and repeat.

You never need to visit more than H + k nodes, where H is the height of the tree. The H comes from the initial descent down the left spine, and k comes from the number of pops before you find the answer.

The solution

def kthSmallest(root, k):
    stack = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right

1. The outer while loop keeps running as long as there are nodes on the stack or curr is not None. This is the standard iterative inorder traversal pattern.
2. The inner while curr loop pushes all left children onto the stack. This navigates to the smallest unvisited node.
3. After popping a node, you decrement k. When k hits 0, you have visited exactly k nodes in sorted order, so the current node holds the answer.
4. If k is still positive, you set curr to the right child. The next iteration of the outer loop will push that right child's left spine onto the stack, continuing the inorder traversal.
5. The function returns as soon as it finds the kth element. It does not traverse the entire tree.

Step-by-step walkthrough

Starting from the BST [5, 3, 6, 2, 4] with k = 3, let's trace the iterative inorder traversal with early stopping.

Notice that nodes 5 and 6 are never visited. The algorithm stops as soon as it finds the 3rd smallest element (4). This early termination is the advantage of the iterative approach.

Complexity analysis

Time is O(H + k) where H is the height of the tree. You spend O(H) descending the left spine initially, then pop k nodes before finding the answer. In the worst case (k = n), this becomes O(n). For a balanced tree with small k, it is O(log n + k).

Space is O(H) for the stack. The stack holds at most one path from the root toward a leaf. For a balanced BST, H = log(n). For a completely skewed tree, H = n.

Building blocks

1. Iterative inorder traversal. The while curr or stack pattern with "push left, pop, go right" is the same pattern used in LeetCode 94 (Binary Tree Inorder Traversal) and LeetCode 173 (BST Iterator). Once you internalize this loop, you can apply it to any problem that needs sorted access to BST values.

2. Early termination with a counter. Instead of collecting all inorder values into a list and returning the kth one, you count pops and stop at k. This turns an O(n) traversal into an O(H + k) one. The same counting trick works in any traversal where you need the kth element.

3. BST sorted order property. The fundamental property that inorder traversal of a BST yields sorted output. This is the reason the problem reduces to "find the kth node in inorder." Recognizing this connection is the first step for any BST problem involving order or rank.

Edge cases

• k = 1: you want the smallest element. The algorithm pushes the entire left spine, pops the leftmost node, and returns immediately.
• k = n (total number of nodes): you want the largest element. The algorithm performs a full inorder traversal, visiting every node before returning the last one. Time becomes O(n).
• Single node tree: the only valid k is 1. The algorithm pushes the root, pops it, decrements k to 0, and returns its value.
• Left-skewed tree (every node only has a left child): the initial left spine push puts all n nodes on the stack. Popping the kth one gives the answer. Space is O(n) since H = n.
• Right-skewed tree (every node only has a right child): the algorithm pushes the root (no left children), pops it (count 1), then moves right. Each step pushes one node and pops one node. The stack never holds more than one element at a time.

From understanding to recall

You now see how finding the kth smallest in a BST reduces to counting nodes during an inorder traversal. The iterative stack approach lets you stop early, and the logic is just the standard inorder loop with a decrement and a check.

But knowing the approach and writing it from memory under pressure are two different things. You need to recall the outer loop condition (while curr or stack), the inner loop that pushes left children, the pop-and-decrement step, and the early return when k hits 0. Miss any piece and the solution breaks.

Spaced repetition closes this gap. You write the iterative inorder traversal with the k counter from scratch, first after one day, then three days, then a week. Each repetition reinforces the muscle memory until the pattern is automatic. The iterative inorder building block alone covers at least half a dozen BST problems, so drilling it once pays off across your entire preparation.

Related problems

• Validate Binary Search Tree - Uses the same inorder BST property to check sorted order
• Binary Tree Inorder Traversal - The iterative stack-based inorder pattern that this solution is built on
• Binary Search Tree Iterator - Splits the same iterative inorder loop into a lazy, on-demand iterator