5.2 Tree Construction

Demo: Construct Binary Tree from Preorder and Inorder Traversal — LC 105 (Medium — Amazon/Google High)

Statement (Demo): Given integer arrays preorder and inorder (the preorder and inorder traversals of a binary tree with unique values), rebuild the tree and return its root. Example: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7] → tree with root 3 | ⚡ n ≤ 3000

Approach: The first preorder element is the root. Its position in inorder splits the left and right subtrees. Store inorder indices in a hashmap so each node costs O(1).

function buildTree(preorder, inorder) {
  const idx = new Map(inorder.map((v, i) => [v, i]));
  let pre = 0;
  const build = (lo, hi) => {
    // the inorder slice [lo, hi]
    if (lo > hi) return null;
    const root = new TreeNode(preorder[pre++]);
    const mid = idx.get(root.val);
    root.left = build(lo, mid - 1);
    root.right = build(mid + 1, hi);
    return root;
  };
  return build(0, inorder.length - 1);
}

Complexity: Time O(n), Space O(n)