STEP 14 · BINARY SEARCH TREES · RECORD THE TURN, NOT THE PATH · MEDIUM

Inorder Successor and Predecessor in BST

WHAT IT SAYS

Given a BST and a target value, find its inorder successor (the smallest value greater than it) and predecessor (the largest value smaller than it).

WHAT IT'S REALLY ASKING

"Walk from the root toward the target. Every time you turn LEFT, the node you're leaving is bigger than the target — a successor candidate, and a better one than any recorded before, since you're descending into smaller territory. The successor isn't found by traversal; it's the last node you turned left at. The search you were doing anyway leaves the answer behind as a footprint."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Inorder traversal, grab the neighbours

O(n) time, O(h) stack — the whole tree, always

Run a full inorder walk — it emits sorted order — and watch for the target: the value emitted just after it is the successor, just before it the predecessor.

WHERE THE WORK IS WASTED — The traversal linearises all n nodes to read off two neighbours — 99 percent of the emission is discarded context. Worse, it ignores that the question is a SEARCH question wearing traversal clothing: 'smallest value above x' is exactly the kind of value-characterised query that BST comparisons answer by steering, one subtree discarded per step. Flattening a search structure to use it as a list forfeits the log — you paid balanced-insertion prices to maintain an ordering, then read it like an unsorted tape.

KEY OBSERVATION — THE UNLOCKlink

Left turns leave successor candidates behind.

Characterise the successor by value: the minimum among all tree values strictly greater than the target x. Now watch what a standard descent toward x does at each node. If the node's value is greater than x, the search goes LEFT — and at that instant, the node being left behind is (a) bigger than x, and (b) smaller than every previously recorded such node, because each new left turn happens deeper inside the previous candidate's LEFT subtree, where everything is smaller than it. So a running variable updated at each left turn — 'candidate = this node, then descend left' — is always the tightest known upper neighbour. If the node's value is ≤ x, everything in its left subtree is also ≤ x — no successor lives there — so descend right, recording nothing. When the descent runs off the tree (or hits x itself and finishes its right-subtree probe), the recorded candidate IS the successor: every value above x either got recorded and superseded, or lives in a subtree the recorded candidates bound more tightly. No candidate ever needs revisiting, which is why the space is O(1) and there is no backtracking. The predecessor is the mirror sentence: right turns leave behind values smaller than x, each tighter than the last; record at right turns, descend left when the node is ≥ x. One structural special case worth internalising because it explains Delete-in-BST: if the target NODE has a right child, its successor is simply the right subtree's minimum — leftmost of the right child — no ancestors involved. The descent-with-recording handles the general case (no right child, successor is an ancestor); the subtree-minimum handles the local case. With parent pointers the two cases become 'walk up until you arrive from a left child', but the from-the-root version needs no parent pointers and costs the same O(h). The move to remember: the search path itself carries the answer. You never traverse; you search for x and keep a one-variable diary of the turns.

One descent, one diary variable each

O(h) time per query, O(1) space, no parent pointers required

Successor: cursor = root, best = null; while cursor: if cursor.val > x, best = cursor, go left; else go right. Return best. Predecessor: flip the comparison and the recorded turn. Both run in the same loop if you want both answers in one pass. If given the node (not the value) and it has a right child, return the right subtree's leftmost instead.

WHAT YOU TRADED — The descent version answers one query in O(h) with nothing stored — but if you need to iterate MANY successors in sequence (an ordered scan), repeated O(h) descents lose to a stack-based iterator that amortises to O(1) per step; know which access pattern you're serving. The transferable lesson: for any 'nearest value above/below' question on an ordered structure, don't traverse — search for the target and record the last time the search stepped over the answer. The path's turns are a free log of the candidates.

WATCH THE IDEA RUN

successor of 7 none yet

left turn records a candidate

right turn records nothing

The successor of 7 is the smallest value still bigger than 7. The tempting move is to find 7 first and then work out where to go. Watch instead what the descent itself hands you for free.

step 1 / 6

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

The Search Path Is the Diary

YOU'LL SEE IT AGAIN WHEN

The query is a value-neighbourhood question — smallest above, largest below, closest to — on a comparison-steerable structure.
Each steering decision that passes over a candidate makes that candidate strictly better than all earlier ones, so one variable suffices.
No recorded candidate is ever revisited or revised downward — the sign that backtracking, stacks, and full traversals are all unnecessary.

SAME BLUEPRINT, DIFFERENT PROBLEM

Delete Node in a BST (the successor swap depends on this)Closest Binary Search Tree ValueLCA of a BST (the same steered descent, different stop rule)BST Iterator (the amortised alternative for sequential access)

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