STEP 14 · BINARY SEARCH TREES · DESCENTS IN THE SORTED STREAM · HARD

Recover BST (Two Nodes Swapped)

WHAT IT SAYS

Exactly two nodes of a BST had their values swapped by mistake. Restore the tree without changing its structure.

WHAT IT'S REALLY ASKING

"A healthy BST's inorder stream climbs steadily upward. Swap two values and the stream stumbles — it DESCENDS somewhere it never should. One stumble if the culprits were inorder-neighbours, two stumbles if they were strangers. The corruption doesn't hide: it announces itself as the exact places the sorted order breaks, and the fix is to swap back what the stumbles point at."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Flatten, sort, and rewrite every node

O(n log n) time, O(n) space, two full passes plus a sort

Inorder-collect all values into an array, sort the array, then run inorder again writing the sorted values back into the nodes in order.

WHERE THE WORK IS WASTED — The sort is a sledgehammer aimed at two loose screws: the collected array is ALREADY sorted except for exactly two positions, and comparison sorting re-derives the order of n-2 elements whose order was never in doubt. The O(n) buffer stores an almost-sorted sequence whose defects a single trailing comparison could have flagged in flight. And rewriting every node's value — even the untouched ones — treats a surgical two-node correction as a full transplant. The problem statement said 'exactly two'; this solution never reads that sentence.

KEY OBSERVATION — THE UNLOCKlink

One swap makes at most two descents in the stream.

Let the healthy inorder sequence be strictly increasing, and suppose values at sorted positions i and j (i < j) got exchanged: the larger value now sits early, the smaller sits late. Scan the corrupted inorder stream with one question — 'did this element fail to exceed its predecessor?' — and case-split on adjacency. If i and j are inorder-adjacent, the stream reads ...a, Y, X, b... where X < Y: exactly ONE descent, at the Y→X boundary, and both culprits are its two endpoints. If they are not adjacent, the stream reads ...Y...X... with correct values between: the FIRST descent happens where Y (too big, too early) exceeds its successor — culprit one is the descent's LEFT element; the SECOND descent happens where X (too small, too late) fails to exceed its predecessor — culprit two is that descent's RIGHT element. Why can't a single swap make three descents? Each misplaced value disturbs the order only at its own borders: Y disturbs the border after it, X the border before it — two borders maximum, and they coincide in the adjacent case. So the detection rule is mechanical: walk inorder with a trailing prev; at the first violation record first = prev and second = current; at any second violation overwrite second = current. After the walk, swap first.val with second.val — the rule covers both cases uniformly because in the adjacent case the second violation simply never arrives, leaving second correctly pointing at the first descent's right element. One pass, one prev pointer, two node references. The 'exactly two swapped' promise is what licenses stopping the diagnosis at two descents — this is Validate BST's monotone-stream check, upgraded from detecting corruption to LOCATING it. The O(1)-space flourish: the walk above still costs O(h) stack. Morris inorder — threading each left subtree's rightmost node back to its root as a temporary return address — delivers the same inorder stream with zero stack, and the prev-comparison rides on top unchanged. The two techniques compose because Morris changed HOW the stream is produced, not WHAT it contains.

Inorder with a trailing prev, record two violations, swap values

O(n) time, O(h) space — or genuinely O(1) with Morris as the stream engine

Walk inorder (recursive, iterative, or Morris) carrying prev. On each visit: if prev exists and prev.val ≥ current.val, then first = prev if unset, and second = current always. After the walk, exchange first.val and second.val. Structure untouched; values restored.

WHAT YOU TRADED — The descent method leans wholly on the 'exactly two nodes' promise — three or more corrupted nodes produce descent patterns this rule mis-diagnoses, while the sort-and-rewrite sledgehammer would still succeed; robustness was traded for precision. Morris buys O(1) space at the price of temporary tree mutation (unsafe under concurrent readers, dangerous with early exits). The transferable lesson: an invariant's canonical linearisation turns 'is it broken?' into 'WHERE is it broken?' — the violations in the stream are coordinates, not just alarms.

WATCH THE IDEA RUN

INORDER STREAM — must only ever climb

—

descents found 0 (max possible: 2)

swap these —

Do not hunt for the two swapped nodes in the tree. Walk it inorder and watch the STREAM: a correct BST emits a strictly increasing sequence, so any corruption has to show up as a place where the sequence goes down.

step 1 / 11

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Violations Are Coordinates

YOU'LL SEE IT AGAIN WHEN

A bounded corruption ('exactly two swapped', 'one element modified') of a structure whose invariant linearises to a monotone stream.
Each misplaced element disturbs only its own borders in the stream, so k corruptions yield at most 2k violations with predictable geometry.
The repair is surgical — swap or rewrite only what violations name — making full re-sorting provably excessive.

SAME BLUEPRINT, DIFFERENT PROBLEM

Validate Binary Search Tree (the same stream, detection only)Morris Traversal (the O(1)-space stream engine)Find the Duplicate / Missing Number (bounded corruption of a known sequence)Kth Smallest in BST (the same inorder stream, different question)

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