Construct Binary Tree from Preorder and Inorder Traversal
Rebuild a binary tree from its preorder and inorder arrays in O(n). The insight — preorder names the root, inorder splits left from right — with code and a trace.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You're handed two flat arrays of numbers and told they came from walking the same binary tree two different ways. Your job: rebuild the exact tree — every node, every left and right pointer — from those two lists alone.
It sounds like there could be a hundred trees that fit. There isn't. A preorder and an inorder traversal together pin down exactly one tree, and the reason why is the whole problem: preorder tells you who the root is, and inorder tells you what falls to its left versus its right. Chase that pair of facts recursively and the tree assembles itself.
The problem
Given two integer arrays — preorder (a preorder traversal: Root → Left → Right) and inorder (an inorder traversal: Left → Root → Right) — build and return the binary tree they describe. Values are unique.
Input: preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
Output (the tree):
3
/ \
9 20
/ \
15 7Two traversal orders, one guaranteed tree. The uniqueness is what makes reconstruction possible: with unique values, every node has a single, findable position in inorder.
The brute force baseline
The recursion below is already the right idea, but a naive version pays a heavy tax at every step: to place a root, it scans the inorder slice to locate the split, and it copies sub-arrays for each recursive call.
function buildTree(preorder, inorder) {
if (inorder.length === 0) return null;
const rootVal = preorder[0];
const root = new TreeNode(rootVal);
const mid = inorder.indexOf(rootVal); // linear scan — the tax
root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));
root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));
return root;
}It returns the correct tree, but indexOf is O(n) and runs once per node, and every slice allocates fresh arrays. On a skewed tree that's O(n) work at each of n levels — O(n²) time, plus a mountain of temporary arrays. The logic is fine; the bookkeeping is wasteful.
The key insight
Two facts do all the work:
- Preorder visits the root first. So the very next unused value in
preorder, scanned strictly left to right, is always the root of whatever subtree you're currently building. - Inorder puts the root in the middle. Once you know the root's value, its position in
inorderis a wall: everything to the left of that index is the left subtree, everything to the right is the right subtree.
Combine them and each node reduces to: grab the next preorder value (root), find its index in inorder (the split), recurse on the left half, recurse on the right half.
Two costs from the brute force vanish if you're careful. The indexOf scan becomes an O(1) hash-map lookup by pre-indexing every inorder value once. And the array slicing disappears if, instead of copying sub-arrays, you pass index bounds into inorder and share a single moving pointer into preorder.
The optimal solution
Build a value → index map for inorder up front. Keep one shared preIdx that only ever moves forward — because preorder consumes roots in exactly the order recursion needs them. The helper takes an inorder [left, right] window.
function buildTree(preorder, inorder) {
let preIdx = 0;
const map = new Map();
for (let i = 0; i < inorder.length; i++) {
map.set(inorder[i], i);
}
function helper(left, right) {
if (left > right) return null; // empty window → no node
const rootVal = preorder[preIdx++]; // next root, then advance
const root = new TreeNode(rootVal);
const mid = map.get(rootVal); // O(1) split point
root.left = helper(left, mid - 1); // build left BEFORE right
root.right = helper(mid + 1, right);
return root;
}
return helper(0, inorder.length - 1);
}The order of the two recursive calls is not cosmetic. Preorder is Root-Left-Right, so after a root is consumed the next preorder values belong to its left subtree. Building root.left first drains those values in the correct sequence; only then does root.right pick up where the left subtree finished. Swap the two lines and every root grabs the wrong value.
preIdx++ advancing globally is what replaces slicing preorder. The map replaces indexOf. What remains is a clean O(1)-per-node recursion.
Walkthrough
Tracing preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]. The map is {9:0, 3:1, 15:2, 20:3, 7:4}. Each row is one helper call, in the order recursion makes them.
| preIdx (before) | Call helper(left,right) | rootVal | mid | Left window | Right window | Result |
|---|---|---|---|---|---|---|
| 0 | helper(0, 4) | 3 | 1 | (0, 0) | (2, 4) | node 3 |
| 1 | helper(0, 0) | 9 | 0 | (0, -1) | (1, 0) | node 9 |
| 2 | helper(0, -1) | — | — | — | — | null (left > right) |
| 2 | helper(1, 0) | — | — | — | — | null (left > right) |
| 2 | helper(2, 4) | 20 | 3 | (2, 2) | (4, 4) | node 20 |
| 3 | helper(2, 2) | 15 | 2 | (2, 1) | (3, 2) | node 15 |
| 4 | helper(2, 1) | — | — | — | — | null |
| 4 | helper(3, 2) | — | — | — | — | null |
| 4 | helper(4, 4) | 7 | 4 | (4, 3) | (5, 4) | node 7 |
| 5 | helper(4, 3) / (5, 4) | — | — | — | — | null, null |
Follow preIdx: it marches 0 → 5, handing out 3, 9, 20, 15, 7 as roots in exactly preorder sequence. Node 3 splits inorder at index 1, giving left window (0,0) (just the 9) and right window (2,4) (the 15, 20, 7). Node 20 in turn splits its window at index 3 into 15 on the left and 7 on the right. The left > right rows are the empty windows that become null leaves — the base case doing its job.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
Brute force (indexOf + slice) | O(n²) | O(n²) | O(n) scan and array copies per node |
| Hash map + index bounds | O(n) | O(n) | O(1) split per node, n nodes; map + recursion stack |
Each of the n nodes does constant work — one preorder read, one map lookup, two recursive calls — so time is O(n). Space is O(n) for the map, plus recursion-stack depth that is O(log n) on a balanced tree but O(n) on a fully skewed one.
Common mistakes
- Recursing right before left. With a single shared
preIdx, the left subtree must consume its preorder values first. Buildingroot.rightbeforeroot.lefthands the wrong values to every node. - Re-scanning inorder with
indexOfinside the recursion. That's the O(n²) trap. Pre-index once into a map and each split is O(1). - Slicing arrays instead of passing bounds. Copying
preorder/inordersub-arrays at every call balloons memory and time. Pass(left, right)index windows and keep the arrays untouched. - Making
preIdxa local variable. It has to persist across all recursive calls (a closure variable or an outer counter). A per-call local resets the root pointer and corrupts the tree. - Forgetting the
left > rightbase case. Without it the recursion reads past the arrays and never terminates the empty branches intonull.
Where this pattern shows up next
The "root splits the range, recurse on each half" shape is the backbone of nearly every binary-tree problem:
- Maximum Depth of Binary Tree — the same post-order recursion, returning a height instead of a node.
- Maximum Depth of Binary Tree - Top Down — carrying depth down as a parameter, the mirror of building a tree up.
- Balanced Binary Tree — comparing left and right subtree heights at every node.
- Diameter of Binary Tree — combining left and right results at each root, exactly like joining subtrees here.
You can also step through the reconstruction interactively to watch preorder hand out roots while inorder splits each range into left and right.
FAQ
Why do you need both preorder and inorder to rebuild the tree?
Neither array alone is enough. Preorder tells you the order roots appear but not how the tree branches — many different trees share the same preorder. Inorder tells you the left-to-right ordering but not which node is a root. Together they're complementary: preorder identifies each root, and inorder uses that root to partition the remaining nodes into left and right subtrees. That combination fixes exactly one tree (when values are unique).
What is the time complexity, and why is it O(n) and not O(n²)?
O(n) time and O(n) space. Each of the n nodes is processed once and does only constant work: read the next preorder value, look up its inorder index in a hash map (O(1)), and issue two recursive calls. The naive version is O(n²) because it locates the root with indexOf — a fresh O(n) scan at every node. Pre-building a value → index map trades O(n) space for O(1) lookups, collapsing the total to linear.
Why must the left subtree be built before the right subtree?
Because a single preIdx pointer is shared across the whole recursion and only moves forward. Preorder is Root-Left-Right, so immediately after consuming a root, the next preorder values are that root's left subtree. Building root.left first drains those values in order; the pointer then sits exactly at the start of the right subtree's values. Reverse the two calls and each node reads a value meant for a different subtree, producing a scrambled tree.
How does the algorithm handle empty subtrees?
Through the left > right base case. When a root sits at the far edge of its inorder window — say a node whose value is the leftmost in its range — one side has no elements, so its window becomes something like (2, 1) where left exceeds right. The helper immediately returns null, creating a missing child. Every leaf is built when both of its recursive calls hit this empty-window case.
Can the same idea reconstruct a tree from postorder and inorder?
Yes, with one adjustment. Postorder is Left-Right-Root, so the root is the last value, not the first. You walk a shared pointer backwards from the end of postorder, and because roots now arrive in Right-before-Left order, you build root.right before root.left. Inorder still supplies the split. The structure is identical — only the pointer direction and the order of the two recursive calls flip.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.