STEP 13 · BINARY TREES · ONE NAMES THE ROOT, ONE SPLITS THE REST · MEDIUM

Construct Binary Tree from Preorder and Inorder

WHAT IT SAYS

Rebuild the unique binary tree whose preorder and inorder traversals are the two given arrays of distinct values.

WHAT IT'S REALLY ASKING

"The two arrays answer different questions, and neither can answer the other's. Preorder tells you WHO — its first element is the root, always. Inorder tells you WHERE — find that root in it, and everything to the left belongs to the left subtree, everything to the right to the right. One identification, one split, and the problem has reproduced itself twice, smaller."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Recurse with array slices and a linear search

O(n^2) time and O(n^2) allocated slice memory in the worst case

Take preorder[0] as the root. Linearly scan inorder for it; say it lands at position k. Slice both arrays: left subtree gets inorder[0..k) and the next k preorder elements; right subtree gets the rest. Recurse on the slices.

WHERE THE WORK IS WASTED — Two independent leaks. The search: every root is hunted by linear scan through its inorder segment, and on a skewed tree each scan covers nearly everything — n scans of average length n/2, re-discovering positions in an array that never changes. Positions of immutable values are a precomputation, not a per-call search. The slices: every recursive call copies its subarrays, but a subarray of a fixed array IS two indices — the copies transport no information the indices didn't, and on a spine they sum to quadratic memory for the privilege.

KEY OBSERVATION — THE UNLOCKlink

Preorder is root-first; inorder is root-in-the-middle. Compose them.

Start from what each traversal MEANS, because the algorithm is nothing but the two definitions run backwards. Preorder emits root, then the whole left subtree, then the whole right subtree. So preorder[0] is the root of everything — no search, it is a definition. But preorder alone cannot tell you where the left subtree's emissions end and the right's begin: [root, A, B] could be both children on the left, both on the right, or one each. The boundary is invisible. Inorder emits left subtree, then root, then right subtree. So the root's POSITION in inorder is exactly that missing boundary: k values sit before it, therefore the left subtree has exactly k nodes — and that count transfers to preorder, whose next k elements after the root must be the left subtree's preorder. Both arrays split perfectly, the two halves are the same problem smaller, and induction finishes it. (Distinctness of values is what makes 'the root's position' well-defined — with duplicates, the split is ambiguous and the tree genuinely isn't unique.) This composition is also why preorder + postorder WITHOUT inorder fails: both name roots, neither locates a split — a one-child node's traversals cannot reveal which side the child hangs on. You need one root-namer and one splitter; inorder is the only splitter. Now kill the two leaks in one stroke each. The search: values are distinct, so build value → inorder-index as a hash map once; every 'find the root' becomes O(1). The copies: represent every subproblem as index ranges into the original arrays — and here is the quiet elegance — you do not even need to track preorder ranges. Preorder's roots are consumed strictly left to right (root before all descendants, and the recursion builds left before right), so a single advancing pointer into preorder, shared across all calls, always rests on the next root. One integer replaces all the slicing arithmetic on one side entirely.

Hash map for the split, advancing pointer for the roots

O(n) time — each node built once, each lookup O(1) — O(n) map plus O(h) stack

Precompute pos[value] = inorder index. Recurse on an inorder range [lo, hi]: if empty, return null; otherwise take preorder[next++] as the root, look up its split point k, build the left child from [lo, k-1] and THEN the right from [k+1, hi] — the order matters, because the shared pointer must consume the left subtree's roots first. Return the root.

WHAT YOU TRADED — The hash map costs O(n) space to convert repeated searches into lookups — the standard trade — and the advancing-pointer trick buys elegance at the price of a hidden ordering contract: build left before right or the pointer desynchronises silently, the kind of bug that produces a wrong tree rather than a crash. The transferable lesson: when reconstructing structure from serialisations, identify what each serialisation uniquely pins down — one must name roots, one must locate splits — and let the recursion be the two definitions inverted.

WATCH THE IDEA RUN

PREORDER — names the root

INORDER — splits the rest

preorder pointer 0 / 5

nodes built 0

Neither array can do this alone. Preorder knows who the root is but not where its subtrees end. Inorder knows where the subtrees end but not who the root is. Each one holds exactly the fact the other is missing.

step 1 / 12

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Root-Namer Plus Splitter

YOU'LL SEE IT AGAIN WHEN

Two linearisations of one structure are given, and each traversal's definition pins down a different degree of freedom — who is the root versus where the parts divide.
A recurring 'find this value's position' over an immutable array — a search that should have been a precomputed index.
Recursive calls pass copied subarrays whose entire content is expressible as two indices into the original.

SAME BLUEPRINT, DIFFERENT PROBLEM

Construct Binary Tree from Postorder and InorderConstruct BST from Preorder (ordering replaces the splitter)Construct Binary Tree from Preorder and Postorder (ambiguous — see why)Serialize and Deserialize Binary Tree (nulls replace the second traversal)

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