Leetcode - 106. Construct Binary Tree from Inorder and Postorder Traversal

Reconstructing a binary tree from its inorder and postorder traversal is a classic recursive problem that tests your understanding of tree traversal patterns and recursion boundaries.

---

🔁 What Are Inorder and Postorder?

• Inorder Traversal (Left → Root → Right)
• Postorder Traversal (Left → Right → Root)

The last node in postorder is always the root of the tree (or subtree).

---

🥇 Approach 1: Basic Recursive with Slicing (Less Efficient)

This version is beginner-friendly and intuitive. It uses array slice() and indexOf(), which makes it less efficient due to repeated array copying and searching.

✅ Code

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

var buildTree = function(inorder, postorder) {
    if (!inorder.length || !postorder.length) return null;

    const rootVal = postorder.pop(); // root from postorder
    const root = new TreeNode(rootVal);

    const mid = inorder.indexOf(rootVal); // find root in inorder

    // Important: build right subtree before left
    root.right = buildTree(inorder.slice(mid + 1), postorder);
    root.left = buildTree(inorder.slice(0, mid), postorder);

    return root;
};

📊 Time & Space Complexity

• Time: O(n²)

  • indexOf() takes O(n) for each node.
  • slice() takes O(n) each time.

• Space: O(n²)

  • Due to array slicing creating new arrays.
  • Call stack can go up to height n.

---

🥈 Approach 2: Optimized Using Hash Map and Index Bounds

Instead of slicing arrays and searching for index each time, we precompute an index map and work with index boundaries. This reduces overhead drastically.

✅ Code

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

var buildTree = function(inorder, postorder) {
    const inorderMap = new Map();
    inorder.forEach((val, idx) => inorderMap.set(val, idx));

    let postIndex = postorder.length - 1;

    function helper(left, right) {
        if (left > right) return null;

        const rootVal = postorder[postIndex--];
        const root = new TreeNode(rootVal);
        const mid = inorderMap.get(rootVal);

        // Build right subtree before left
        root.right = helper(mid + 1, right);
        root.left = helper(left, mid - 1);

        return root;
    }

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

📊 Time & Space Complexity

• Time: O(n)

  • Each node is processed once.
  • Index lookup is O(1) using a map.

• Space: O(n)

  • For the map and recursion stack.

---

🧠 Summary Comparison

Feature	Basic Approach	Optimized Approach
Slicing Arrays	✅ Yes	❌ No
Uses Hash Map	❌ No	✅ Yes
Time Complexity	❌ O(n²)	✅ O(n)
Space Complexity	❌ O(n²)	✅ O(n)
Easy to Understand	✅ Yes	⚠️ Moderate

---

✨ Final Thoughts

• The basic version is great for interviews when you’re warming up or proving your logic.
• The optimized version is best for production-level or performance-critical use cases.