Construct Binary Tree from Preorder and Inorder Traversal

MediumTreesArrayTreeDivide and Conquer

Problem

You are given two arrays describing the same binary tree, with all node values distinct: one its preorder traversal, the other its inorder traversal. Reconstruct the tree they came from and return its root.

Example. With preorder [3, 9, 20, 15, 7] and inorder [9, 3, 15, 20, 7], the tree has root 3, a left child 9 that is a leaf, and a right child 20 whose own children are 15 and 7.

Key idea

Neither array alone reveals tree levels or shape, so building level by level does not work. The insight is to use what each order guarantees separately: preorder lists a subtree's root before its left or right subtree, so the first value remaining in a preorder slice is always that slice's root. Inorder lists a subtree's left descendants, then its root, then its right descendants, so once the root's value is known, its position in the matching inorder slice splits that slice into the left and right subtree's values, and their counts split the preorder slice too.

Recursing on this (take the next preorder value as the root, locate it in the current inorder range to split left from right, then recurse on each half) rebuilds the tree one root at a time. A hash map from value to inorder index makes each split a constant-time lookup.

Solution

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 indexOf = new Map<number, number>();
  inorder.forEach((val, idx) => indexOf.set(val, idx));

  let preorderIndex = 0;

  function build(inorderLeft: number, inorderRight: number): TreeNode | null {
    if (inorderLeft > inorderRight) {
      return null;
    }

    // The next unused preorder value is always the root of the current subtree.
    const rootVal = preorder[preorderIndex];
    preorderIndex++;

    // The root's position in the inorder range splits it into left and right subtree values.
    const rootIndex = indexOf.get(rootVal)!;
    const node = new TreeNode(rootVal);
    node.left = build(inorderLeft, rootIndex - 1);
    node.right = build(rootIndex + 1, inorderRight);
    return node;
  }

  return build(0, inorder.length - 1);
}

Complexity

  • Time: O(n). With the index map, every node is created and located in constant time.
  • Space: O(n). The index map, plus O(h) for the recursion stack.

Watch out for

  • Skipping the index map and scanning for the root's position each call degrades the algorithm to O(n²).
  • Track subtrees as index ranges into the original arrays rather than copying subarrays, which also costs O(n²).
  • The technique assumes no duplicate values; a repeated value makes the position lookup ambiguous.

Pattern

This is divide-and-conquer reconstruction: one traversal locates each root, the other partitions remaining values into subproblems. The same idea rebuilds a tree from postorder and inorder traversals.

Related questions