STEP 14 · BINARY SEARCH TREES · INORDER IS SORTED — STOP EARLY · MEDIUM

Kth Smallest and Largest Element in a BST

WHAT IT SAYS

Find the k-th smallest (or k-th largest) value in a binary search tree.

WHAT IT'S REALLY ASKING

"A BST's inorder traversal doesn't PRODUCE sorted order — it IS sorted order, walked in place. So the k-th smallest is simply the k-th node the inorder walk visits. The only real question is discipline: can you stop at the k-th visit instead of collecting all n and indexing?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Flatten to an array, then index

O(n) time, O(n) space, always

Run a full inorder traversal appending every value to a list — which comes out sorted — and return list[k-1]. For k-th largest, return list[n-k].

WHERE THE WORK IS WASTED — Two leaks with one cause. If k is 3 and the tree holds a million nodes, the walk visits 999,997 nodes purely to append values the answer will never touch — the traversal has no idea it could have stopped, because collection and selection were separated into two phases. And the O(n) buffer exists only to bridge those phases: the k-th visit could have been RECOGNISED at the moment it happened, with a counter, making the array a container for information you needed for exactly one instant.

KEY OBSERVATION — THE UNLOCKlink

The k-th inorder visit is the answer. Count visits.

First the foundational fact, argued rather than asserted: inorder on a BST emits sorted order because the traversal's structure IS the invariant's structure. Inorder says left-subtree, node, right-subtree; the BST property says everything-smaller, node, everything-larger. They are the same sentence. Induction closes it: if both subtrees emit sorted and every left value precedes the node precedes every right value, the whole emission is sorted. So 'k-th smallest' translates to 'the k-th node inorder touches' — and that is a streaming question, not a storage question. Carry a counter; at each inorder VISIT (the moment between the left and right recursions), decrement k; when it hits zero, the current node is the answer and every remaining subtree is irrelevant. The abort propagates: once found, each pending recursion returns immediately without descending. Cost: the walk touches the k-th node's left-spine ancestry plus the k nodes themselves — O(h + k), which for small k on a balanced tree is barely more than a root-to-leaf path. K-th LARGEST needs no new idea, only a mirror: reverse inorder (right, node, left) emits descending order, so the same counter trick finds it in O(h + k) from the other end. Resist the translation 'k-th largest = (n-k+1)-th smallest' — it works, but it forces you to know n, and if you must count the tree first you've paid O(n) and lost the early exit. The follow-up that interviews love, because it changes the data structure rather than the algorithm: many queries on a mutating tree. Augment each node with the size of its subtree. Then each query is a single descent — if the left subtree holds L nodes, the current node is the (L+1)-th smallest: k ≤ L means recurse left; k = L+1 means found; otherwise recurse right with k - L - 1. O(h) per query with no traversal at all, and insertions maintain the counts along their own O(h) path. The moment 'find the k-th' becomes a repeated question, the answer moves from a clever walk to a smarter node.

Inorder with a countdown, mirrored for largest

O(h + k) time, O(h) space for one query; O(h) per query with size augmentation

Recursive: inorder walk decrementing k at each visit; record and short-circuit when k reaches zero. Iterative: the explicit-stack inorder — push left spine, pop, count, step right — which makes the early exit a plain return. K-th largest: identical with the two child directions swapped. Repeated queries: subtree-size augmentation and a single steered descent.

WHAT YOU TRADED — The streaming walk is optimal for one query but pays O(h + k) every time — amortising across many queries requires the size augmentation, which costs one integer per node and a maintenance obligation on every insert and delete (forget one path update and every subsequent query silently lies). The transferable lesson: when a structure's canonical traversal emits a meaningful order, selection questions become counting questions — and if the question repeats, move the count into the structure itself.

WATCH THE IDEA RUN

THE INORDER STREAM — already sorted, for free

—

visits counted 0 / k=3

nodes never touched …

Do not sort the tree. Do not collect its values. An inorder walk of a BST already emits them in sorted order — the sorting is not something you do, it is something the structure already did.

step 1 / 5

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Count Visits in the Canonical Order

YOU'LL SEE IT AGAIN WHEN

The structure has a traversal whose emission order is exactly the order the question ranks by — sorted, by time, by priority.
The answer needs one element of that order, so materialising the full sequence buffers n items to use one.
Queries repeat against a mutating structure — the signal to cache per-node counts (subtree sizes) and steer instead of walk.

SAME BLUEPRINT, DIFFERENT PROBLEM

Inorder Successor in BSTValidate Binary Search Tree (the same inorder stream, different predicate)Kth Largest Element in a Stream (heap as the alternative when there is no tree)Order Statistic Tree / Count of Smaller Numbers After Self

The bar isn't "solved it once." It's "could rebuild it from the observation."