Build from traversals
Preorder gives the root; inorder splits left from right.
The index map makes each split O(1); the preorder cursor only moves forward.
01The intuition
Start with what you would do by hand
Someone walked a tree twice and wrote down the nodes in two different orders. Preorder, "me first, then my left side, then my right side", gave [3, 9, 20, 15, 7]. Inorder, "left side, then me, then right side", gave [9, 3, 15, 20, 7]. Can you rebuild the tree from the two lists? Yes, and the by-hand reasoning is the algorithm, so let us do it slowly.
Preorder always writes the root first, so the root is 3. Now find 3 in the inorder list: it is at position 1. Everything left of it in inorder, [9], is the left subtree; everything right of it, [15, 20, 7], is the right subtree. Now repeat on each part. The slow part by hand is "find 3 in the inorder list": scanning the list for every node costs about n steps each, n2 in total.
Build the structure, one piece at a time
Piece one: a cursor into the preorder list. It starts at 0 and only ever moves forward by one each time we place a node. Whatever it points at is the root of the subtree we are currently building. We never have to search preorder.
Piece two: a lookup table from value to inorder position, built once: {9:0, 3:1, 15:2, 20:3, 7:4}. Now "find 3 in inorder" is a single lookup instead of a scan. This needs distinct values, which the problems guarantee.
Piece three: build a subtree from an inorder slice [lo, hi]. If the slice is empty, return nothing. Otherwise take the value under the cursor, advance the cursor, look up its inorder index m, then build the left child from [lo, m − 1] and the right child from [m + 1, hi]. Left before right, because that is the order preorder listed them.
| Cursor value | Inorder index | Left slice | Right slice |
|---|---|---|---|
| 3 | 1 | [0, 0] | [2, 4] |
| 9 | 0 | empty | empty |
| 20 | 3 | [2, 2] | [4, 4] |
| 15 | 2 | empty | empty |
| 7 | 4 | empty | empty |
Read the rows top to bottom and you see the cursor hand out 3, 9, 20, 15, 7 in preorder, each landing in the slice that inorder reserved for it.
Why it is correct
Two facts about traversals do all the work. First, in preorder the root of any subtree is written before every node of that subtree, so when we start building a subtree the cursor is on its root. Second, in inorder the root of a subtree sits between its left-subtree nodes and its right-subtree nodes, so the inorder position splits the slice exactly. Because we build the left subtree completely before touching the right, and preorder lists the whole left subtree before the right, the cursor arrives at the right subtree's root exactly when we need it.
size(left) = m − lo, size(right) = hi − m, and the cursor advances by exactly size(left) + 1 before the right subtree begins
With inorder and postorder the same idea runs the cursor backwards from the end, building right before left, because postorder writes the root last.
Why it is fast
Building the lookup table costs n insertions. Each node is placed exactly once with one lookup and two slice computations, all constant time. Total O(n), against the by-hand n2 from rescanning inorder for every node. The recursion depth is the height, O(h).
How to recognise it in an interview
"Construct the tree from its preorder and inorder", "deserialize", "verify a serialization", or any task where you are handed a traversal and must recover structure. Say: "Preorder gives me the root through a forward-moving cursor; inorder tells me how many nodes go left, so I split the slice there with a precomputed index map." Construct Binary Tree from Preorder and Inorder Traversal is the direct form. Serialize and Deserialize Binary Tree is the same cursor idea with explicit null markers instead of a second list, so no index map is needed.
02The idea in one line
Preorder gives the root; inorder splits left from right.
Reach for it when: Construct from pre+in, post+in, pre+post, BST from preorder, serialize/deserialize.
Cost: O(n) time.
03The walk-through, step by step
The video works one example: Build from preorder [3,9,20,15,7], inorder [9,3,15,20,7]. These are its captions in order, so you can follow without the video or check a step you missed.
- Preorder gives roots in order; inorder tells what lies left and right
- Cursor says the next root is 3; inorder index 1
- Place 3: left gets inorder[0..0], right gets [2..4]
- Cursor says the next root is 9; inorder index 0
- Place 9: left gets inorder[0..-1], right gets [1..0]
- Cursor says the next root is 20; inorder index 3
- Place 20: left gets inorder[2..2], right gets [4..4]
- Cursor says the next root is 15; inorder index 2
- Place 15: left gets inorder[2..1], right gets [3..2]
- Cursor says the next root is 7; inorder index 4
- Place 7: left gets inorder[4..3], right gets [5..4]
- Cursor exhausted: the tree is complete
- Each node placed once with an O(1) index lookup: O(n)
04Asked at Google
8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Construct Binary Tree from Preorder and Inorder Traversal | Medium | 38 | last 6 months |
| Serialize and Deserialize Binary Tree | Hard | 38 | last 6 months |
| Construct Binary Tree from Preorder and Postorder Traversal | Medium | 26 | |
| Construct Binary Tree from Inorder and Postorder Traversal | Medium | 23 | last 6 months |
| Construct Binary Search Tree from Preorder Traversal | Medium | 22 | |
| Verify Preorder Serialization of a Binary Tree | Medium | 21 | |
| Recover a Tree From Preorder Traversal | Hard | 18 | |
| Serialize and Deserialize BST | Medium | 6 |
05Related patterns
Other patterns in Trees: Recursive DFS (post-order fold), Best path through each node, Level-order BFS, Root-to-leaf path carry, Lowest common ancestor, Iterative traversal with a stack, Column / coordinate traversal, Rerooting DP (sum over all roots), Post-order deletion / pruning, Tree as a graph (parent pointers), Tree DP: take or skip this node, Serialize / deserialize by BFS.