105. Construct Binary Tree from Preorder and Inorder Traversal

Given the preorder and inorder traversals of a binary tree with unique values, rebuild and return the tree.

The next pre-order value is always the root of the current subtree. Its position in the inorder array splits the remaining values into left and right subtrees. A value → index map makes that lookup O(1).

1function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
2  const idx = new Map(inorder.map((v, i) => [v, i]));
3  let p = 0;
4  function go(lo: number, hi: number): TreeNode | null {
5    if (lo > hi) return null;
6    const node = new TreeNode(preorder[p++]);
7    const mid = idx.get(node.val)!;
8    node.left = go(lo, mid - 1);
9    node.right = go(mid + 1, hi);
10    return node;
11  }
12  return go(0, inorder.length - 1);
13}

preorder

inorder

tree so far

Next pre-order value 3 is the root of inorder[0..4].

1 / 0

Space: play/pause · ←/→: step