0
preIdx
Preorder hands you the roots in order; inorder tells you what falls left vs right of each root. Consume preorder front-to-back as a pointer and split inorder around each root — an index map makes every split O(1).
Given preorder and inorder traversals of a binary tree with unique values, rebuild the exact tree. preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] → 3 is the root, with 9 on the left and 20 (15,7) on the right. Return that tree (its level-order form is [3,9,20,null,null,15,7]).
root, left…, right…, a single advancing pointerpreIdx over preorder always points at the next root — you never need to slice preorder, only inorder.Map<value, index>so "where is this root in inorder?" is O(1) instead of a linear scan.preorder[preIdx++]; that value is the current subtree's root. The post-increment is what threads the roots in correct order.mid = pos[root]. Inorder [lo..mid-1] is the left subtree; [mid+1..hi] is the right.preIdx reaches the right root at the right time.lo > hi ⇒ empty range ⇒ return null.preIdx would grab the next root for the wrong side. The two recursive calls are NOT interchangeable here even though they look symmetric.Without it, each recursion does an O(n) linear search for the root inside inorder, giving O(n²) overall (worst on a linear/skewed tree). The hash-map drops the per-node split to O(1), so total work is O(n). Recursion depth is the tree height, O(h), up to O(n) for a skewed tree.
preorder left to right. Each value is the root of the next subtree; split inorder around it into left and right.class TreeNode {
val: number;
left: TreeNode | null = null;
right: TreeNode | null = null;
constructor(val: number) {
this.val = val;
}
}
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
// Map each value to its index in inorder for O(1) splits.
const pos = new Map<number, number>();
inorder.forEach((v, i) => pos.set(v, i));
let preIdx = 0; // next root to consume from preorder
// Build the subtree whose inorder values are inorder[lo..hi].
function build(lo: number, hi: number): TreeNode | null {
if (lo > hi) return null; // empty range → no node
const rootVal = preorder[preIdx++]; // preorder front = this root
const root = new TreeNode(rootVal);
const mid = pos.get(rootVal)!; // where root sits in inorder
root.left = build(lo, mid - 1); // left subtree first…
root.right = build(mid + 1, hi); // …because preorder is root,L,R
return root;
}
return build(0, inorder.length - 1);
}pos maps each value to its position in inorder. This is the optimization that turns the per-node split from an O(n) scan into an O(1) lookup.preIdx lives outside the recursion. Every call grabs the next root with preorder[preIdx++] — no need to pass or slice preorder ranges around.lo > himeans the inorder window is empty, so this child doesn't exist → null. Don't touch preIdx here.mid = pos.get(rootVal) is where the root sits in inorder. Left subtree = [lo, mid-1], right subtree = [mid+1, hi].preIdxmarch through every left node before it reaches the right subtree's root. Reversing these two lines breaks the tree.preIdx keep it O(n).| given preorder + inorder of a tree | root = preorder front, split inorder |
| "find root inside inorder fast" | Map<value, inorderIndex> |
| no array slicing wanted | shared preIdx pointer + [lo,hi] ranges |
| postorder + inorder variant | root from back, recurse right-then-left |
const pos = new Map<number, number>();
inorder.forEach((v, i) => pos.set(v, i));
let preIdx = 0;
function build(lo: number, hi: number): TreeNode | null {
if (lo > hi) return null;
const root = new TreeNode(preorder[preIdx++]);
const mid = pos.get(root.val)!;
root.left = build(lo, mid - 1);
root.right = build(mid + 1, hi);
return root;
}
return build(0, inorder.length - 1);preorder— its first element is always the current subtree's root.