STEP 14 · BINARY SEARCH TREES · THE ORDERING IS THE SPLITTER · MEDIUM

Construct BST from Preorder Traversal

WHAT IT SAYS

Rebuild the unique BST whose preorder traversal is the given array.

WHAT IT'S REALLY ASKING

"Rebuilding a plain binary tree needed TWO traversals — one to name roots, one to locate splits. A BST's split point isn't information you need delivered; it's implied: everything smaller than the root goes left, everything larger goes right. The second traversal was doing a job the invariant does for free. One array suffices — if you can find the split without scanning for it."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Insert each element into a growing BST

O(n·h) — O(n log n) if the result is balanced, O(n^2) if skewed

Walk the preorder array left to right, inserting each value with the standard BST insertion. Preorder visits roots before descendants, so each insertion lands where the original tree had it.

WHERE THE WORK IS WASTED — Each insertion re-descends from the root, re-comparing against ancestors the previous insertions already compared against — the shared path prefixes are walked again and again, and a sorted input degrades the whole thing to quadratic. But the deeper waste is informational: insertion treats each value as arriving from nowhere, when the array's ORDER is screaming context. Preorder guarantees each value belongs in the subtree of the most recent ancestor it fits under — the array position already encodes the destination's neighbourhood, and root-restarts ignore it.

KEY OBSERVATION — THE UNLOCKlink

A value past its bound belongs to an ancestor.

First see why one traversal is enough, where the general tree needed two. In the preorder+inorder construction, preorder named each root and inorder located the split — how many elements go left. For a BST, the split is determined by VALUE: given root r, the left subtree's preorder is exactly the run of following elements smaller than r, and the right subtree's is the rest. The inorder array was a courier delivering information the invariant already implies. (This also explains why BST serialization can skip null markers: values carry the structure.) The naive use of that insight scans forward from each root to find where the smaller-run ends — correct, O(n^2) on a spine, and it inverts the question badly. Instead of each root asking 'where do my children end?', let each CHILD ask 'do I belong here?'. That inversion is the algorithm. Give every recursive call an upper bound: 'build the largest subtree you can from the stream, using only values below this bound'. One shared pointer advances through the array. The call peeks at the current value — if it exceeds the bound, this value belongs to some ANCESTOR's right subtree, so return null WITHOUT consuming it and let the recursion unwind until the frame whose bound accepts it. If it fits, consume it as the root, build the left child with the root's own value as the tighter bound (left descendants must stay below the root), then the right child with the inherited bound (right descendants are limited only by whatever ancestor constraint applies). Why linear: every array element is consumed exactly once, and every REJECTION immediately terminates a call — each element causes at most one rejection per unwinding frame, and each frame is created once. The bound plays the same role as in Validate BST, run in reverse: there, bounds checked a tree against a stream; here, bounds carve a stream into a tree. Same invariant, both directions.

One pointer, one bound, recursion unwinds on rejection

O(n) time — each element consumed once, rejected O(1) amortised — O(h) stack

build(bound): if the pointer is past the end or the current value exceeds bound, return null. Otherwise consume the value as a node, set node.left = build(node.val), node.right = build(bound), return node. Call build(infinity). The stack-based iterative version (each new value: pop stack while smaller-bound tops, attach) is the same logic with the recursion made explicit.

WHAT YOU TRADED — The upper-bound recursion is linear but subtle — the 'reject without consuming' step is the entire mechanism, and off-by-one thinking there produces silently wrong trees; the insert-one-by-one version is unmissably correct and fine when n is small or the tree is known balanced. The transferable lesson: when a structure's invariant IMPLIES information a second input was supplying, delete the second input — and when a per-parent scan inverts into a per-child bound check, quadratic often collapses to linear.

WATCH THE IDEA RUN

PREORDER — one pointer, never rewound

0next

ceiling for this slot +∞

nodes placed 0 / 6

Sorting the preorder gives you the inorder, and then you can reuse the two-array construction — O(n log n), and it needs the second array. But a BST's preorder is not just a list of values. It already knows where every subtree ends. You only have to notice how.

step 1 / 13

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Let the Invariant Replace the Second Input

YOU'LL SEE IT AGAIN WHEN

Reconstruction from one linearisation is suddenly possible because a value-based invariant determines what structure alone could not.
A forward scan 'find where my segment ends' per node can be inverted into 'does this element belong to me?' per element — bound-passing instead of searching.
Rejected elements are not consumed; the recursion unwinds until some ancestor's bound accepts them — the stream and the stack stay synchronised.

SAME BLUEPRINT, DIFFERENT PROBLEM

Construct Binary Tree from Preorder and Inorder (the two-input version)Validate Binary Search Tree (the same bounds, checking instead of building)Serialize and Deserialize BSTLargest Rectangle in Histogram (the same pop-while-smaller stack shape)

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