Frontend Beauty
ESC

Type to search the knowledge base.

Construct Tree from Preorder Inorder

Rebuild a binary tree from preorder and inorder arrays — root split, index map, and O(n) recursive construction.

advanced3 min read
  • dsa
  • tree
  • interview
  • Google
  • Meta

The problem

Unique node values. Given preorder and inorder traversals, reconstruct the binary tree.

preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]

      3
     / \
    9  20
      /  \
     15   7

Why both arrays?

  • Preorder: root, then left subtree, then right.
  • Inorder: left, root, right → root’s index splits left/right sizes.

Either alone is ambiguous for general binary trees.

Brute: scan inorder every time

For each root, linear search in inorder slice. O(n²).

Optimal: hashmap of value → inorder index

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  const idx = new Map<number, number>();
  inorder.forEach((v, i) => idx.set(v, i));
  let pre = 0;

  function build(lo: number, hi: number): TreeNode | null {
    if (lo > hi) return null;
    const rootVal = preorder[pre++];
    const root = new TreeNode(rootVal);
    const mid = idx.get(rootVal)!;
    root.left = build(lo, mid - 1);
    root.right = build(mid + 1, hi);
    return root;
  }

  return build(0, inorder.length - 1);
}
Time O(n)
Space O(n) map + O(h) stack

Order matters: build left before right so pre consumes preorder in sequence.

Walk

pre points at 3 → mid in inorder = 1 → left inorder [9], right [15,20,7]
left: pre=9 → leaf
right: pre=20 → mid splits 15 | 7, etc.

Edge cases

  • Empty arrays → null
  • Single node
  • Skewed left / right only
  • Values must be unique for this map approach (problem guarantees)

Common mistakes

  • Building right before left with a shared pre index
  • Copying array slices every call (O(n²) time/space) instead of index ranges
  • Off-by-one on lo > hi

Interview delivery

  1. Preorder gives root; inorder splits.
  2. Map for O(1) split index.
  3. Recurse ranges; left then right.
  4. O(n).
  5. Optional: postorder+inorder variant.

Mental model

Preorder always hands you the next root of the current subtree. Inorder tells you how many nodes belong left of that root. Index ranges replace array slicing so each node is processed once.

Drawing one example on the whiteboard is worth more than memorizing the signature. Point at preorder cursor, find root in inorder, recurse left range, recurse right range.

  • Postorder + inorder: root is last in postorder; build right before left if using a reverse cursor.
  • Preorder + postorder: possible for full trees with unique shapes under constraints; harder.
  • Serialize/deserialize: choose a format that encodes nulls so structure is unambiguous.

Out-loud answer

“Preorder gives roots in order; inorder splits left/right sizes. Hash value→inorder index for O(1) splits. Recurse with lo/hi bounds, consume preorder left-to-right. O(n) time and space. Values unique.”

Further reading