Trees · LC #105
Construct Binary Tree from Preorder and Inorder Traversal
Reconstruct a unique binary tree given its preorder and inorder traversal arrays. Preorder identifies the root; inorder splits the remaining nodes into left and right subtrees.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree.
Sample I/O
Input: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7] Output: [3,9,20,null,null,15,7]
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
Recursion works because preorder always gives the root first, and inorder tells us exactly which nodes are in the left vs right subtrees. These two facts together uniquely determine the tree at every level of recursion.
Core Concept
Build a hashmap of inorder value → index for O(1) lookups. Maintain a preorder index pointer. Recursive `build(l, r)`: consume next preorder value as root, find its inorder index `mid`, recurse `build(l, mid-1)` for left subtree, `build(mid+1, r)` for right subtree. Base case: l > r → null.
When to use
Tree reconstruction from traversal pairs (preorder+inorder, postorder+inorder), any problem requiring building a tree from its traversal sequences.
When NOT to use
When only one traversal is given (can't uniquely reconstruct without both, unless it's a BST). When duplicates exist - inorder hashmap breaks (need index-based approach).
Key Insights
What to Know Cold
- Preorder[0] is always the root. After picking root, its inorder index splits left/right.
- Hashmap for inorder lookup is critical - naive linear search makes it O(n²).
- The number of left subtree nodes = `mid - l`, used to bound left preorder segment.
- Preorder index increments globally (not per-subtree) - must use a shared pointer or closure.
- Unique reconstruction guaranteed only when all values are distinct.
1 example
Worked Examples
Three-level tree reconstruction
preorder=[3,9,20,15,7], inorder=[9,3,15,20,7].
Root=3 (preorder[0]). inorder index of 3 = 1. Left: inorder[0..0]=[9], preorder next=9 → leaf. Right: inorder[2..4]=[15,20,7], preorder next=20 → root with 15 left, 7 right.
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
const inMap = new Map(inorder.map((v, i) => [v, i]));
let idx = 0;
function build(l: number, r: number): TreeNode|null {
if (l > r) return null;
const val = preorder[idx++];
const node = new TreeNode(val);
const mid = inMap.get(val)!;
node.left = build(l, mid - 1);
node.right = build(mid + 1, r);
return node;
}
return build(0, inorder.length - 1);
}Output: [3,9,20,null,null,15,7]
Demonstrates shared index pointer pattern - preorder consumed left-to-right.