5.2 Tree Construction

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

Statement (Demo): integer array preorder ও inorder দেওয়া (একটা binary tree-এর preorder ও inorder traversal) — সেই binary tree টি reconstruct করে root return করুন। সব node-এর মান unique। উদাহরণ: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7] → tree with root 3 | ⚡ n ≤ 3000

Approach: preorder-এর প্রথম এলিমেন্ট = root। inorder-এ সেই root-এর position বাম/ডান subtree ভাগ করে দেয়। inorder index গুলো hashmap-এ রাখলে প্রতি নোড O(1)।

function buildTree(preorder, inorder) {
  const idx = new Map(inorder.map((v, i) => [v, i]));
  let pre = 0;
  const build = (lo, hi) => {
    // inorder-এর [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)