52. Kth Smallest in a BST

Problem

Fin might index cached KB entries or retrieval candidates in a binary search tree keyed by a sortable field (e.g. last-accessed time, or a numeric relevance score) for fast ordered range queries.

Given such a BST and a rank k, find the k-th smallest key in the tree without doing a full traversal into a sorted list first. k is 1-indexed: k=1 means the smallest value in the tree.

Source: src/52_kth_smallest_in_bst.py

class TreeNode:
    def __init__(self, val=0, left=None, right=None): ...

def kth_smallest(root: TreeNode, k: int) -> int: ...

# BST:      5
#          / \
#         3   7
#        / \   \
#       2   4   8
kth_smallest(root, 1)  # -> 2  (smallest value)
kth_smallest(root, 4)  # -> 5  (the 4th smallest, in sorted order 2,3,4,5,7,8)

Step-by-Step Approach

1. Recall the core BST property: for any node, an in-order traversal (left, node, right) visits every node in strictly ascending sorted order. That means the k-th smallest value is simply the k-th node visited by an in-order traversal — no sorting needed afterward.
2. Instead of a recursive traversal (which visits the whole tree before you can stop), use an explicit stack to simulate in-order traversal iteratively, so the walk can be paused and inspected one step at a time.
3. Push every left child onto the stack while descending, until hitting a None — that reaches the leftmost (smallest) unvisited node.
4. Pop a node off the stack: this is the next node in ascending order. Increment a visited counter. If the counter now equals k, this popped node's value is the answer — return immediately.
5. Otherwise, move to the popped node's right child and repeat the "push all left children" descent from there, since after visiting a node, in-order traversal moves into its right subtree next.
6. If the stack empties and the loop ends without ever hitting the counter, k was larger than the number of nodes in the tree — raise an error rather than returning a bogus value.

The key insight is that in-order traversal of a BST is already sorted-order for free — the trick is stopping the instant the k-th node is popped off the explicit stack, rather than building a full sorted list and then indexing into it. In the worst case (k is large, or the tree is skewed) this still touches close to every node, but for small k against a large tree it can terminate far earlier than a full traversal would, and it never needs O(n) extra space for a sorted-value list.

Reference solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def kth_smallest(root, k):
    # iterative in-order traversal with early termination, O(h + k) time, O(h) space
    stack = []
    node = root
    count = 0
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        count += 1
        if count == k:
            return node.val
        node = node.right
    raise ValueError("k is larger than the number of nodes in the tree")

Key Functions & Tricks

• Explicit stack + while stack or node — simulates recursive in-order traversal iteratively, so it can be interrupted mid-walk.
• Inner while node: stack.append(node); node = node.left — descends to the next unvisited leftmost node before popping.
• Early return the instant count == k — avoids visiting nodes past the answer, unlike collect-then-sort.
• BST in-order property — left, node, right always yields ascending sorted order for a valid BST, with no comparisons or sorting needed.
• raise ValueError(...) after the loop — signals an out-of-range k instead of silently returning nothing.

How to Recognize This Pattern