Construct Binary Tree from Preorder and Inorder Traversal is the classic "rebuild the tree" problem. It teaches you to read two traversal orders as a pair of clues that, together, pin down exactly one tree.
Problem. Given two integer arrays preorder and inorder — the preorder and inorder traversals of
the same binary tree (all values distinct) — reconstruct and return the tree.
Example: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7] → the tree with root 3, left
child 9, right child 20, and 20 having children 15 and 7.
The slow way first
You could try to guess a tree, run both traversals on it, and check whether they match — but the number of possible trees explodes, so brute force is hopeless. The good news is we never have to guess. The two traversal orders contain enough structure to rebuild the tree directly.
The question to ask: what does each traversal order tell me for free? Preorder visits root first. Inorder visits left subtree, then root, then right subtree. Put those two facts together and the tree falls out.
The idea: root from preorder, split with inorder
preorder[0] is always the root of the whole tree. Now find that root value inside inorder. Everything to its left in inorder is the left subtree; everything to its right is the right subtree. Recurse on each half, consuming preorder elements left to right.
The key insight: preorder gives you which node comes next; inorder tells you how to split its children. A value-to-index map on inorder makes the split an O(1) lookup instead of a scan.
Walk through it
Step through the animation. The top row is preorder, the bottom row is inorder. We pull 3 as the root, find it in inorder to see 9 on the left and 15, 20, 7 on the right, then keep pulling the next preorder value (9, then 20, then 15, then 7) and splitting each inorder slice the same way. The tree fills in node by node.
Pseudocode
pos = map from each inorder value -> its index
i = 0 # walks across preorder
build(lo, hi): # inorder slice [lo .. hi]
if lo > hi: return None # empty slice -> no node
val = preorder[i]; i += 1 # next preorder value is this root
node = new Node(val)
node.left = build(lo, pos[val] - 1) # items left of root in inorder
node.right = build(pos[val] + 1, hi) # items right of root in inorder
return node
return build(0, len(inorder) - 1)The Python solution
def build(preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
self.i = 0
def helper(lo, hi):
if lo > hi:
return None
val = preorder[self.i]
self.i += 1
node = TreeNode(val)
node.left = helper(lo, pos[val] - 1)
node.right = helper(pos[val] + 1, hi)
return node
return helper(0, len(inorder) - 1)posmaps each inorder value to its index, so finding the root inside inorder is O(1).self.iis a shared cursor that walks across preorder; every recursive call consumes exactly one preorder value as a root.helper(lo, hi)builds the subtree whose inorder values fill the rangelo..hi. An empty range (lo > hi) means no node.val = preorder[self.i]grabs the next root; we build it, then recurse left first (matching preorder order).pos[val] - 1is the right end of the left slice;pos[val] + 1is the left end of the right slice.
Complexity
| Case | Time | Notes |
|---|---|---|
| Without the index map | O(n²) (slow) | scanning inorder for each root |
| With the value -> index map | O(n) (moderate) | each node built once, O(1) split |
O(n) (moderate)We build each of the n nodes exactly once, and the pos map turns the "find the root in inorder" step from a scan into an O(1) lookup. The extra space is the map plus the recursion stack.
When this pattern shows up
Any "rebuild / reconstruct the tree from traversals" problem is the same move: one traversal tells you the next root, another tells you where to split its children. Preorder+inorder, postorder+inorder, and serialized-tree problems all reduce to this root-then-split recursion.
Recurse left before right, because preorder lists the entire left subtree before the right. Advance the shared preorder cursor exactly once per node — building the right child before the left would hand it the wrong preorder value.
Practice
After taking 3 as the root and finding it in inorder = [9, 3, 15, 20, 7], which values form the left subtree and which form the right?
1. Which traversal tells you the next root, and which tells you how to split?
2. Why build a value -> index map over inorder?
3. Why must we recurse into the left child before the right child?
4. What is the overall time complexity with the index map?