The O(n) Club: How to Actually Rebuild a Binary Tree from Inorder and Postorder (Without Crying)

The O(n) Club: How to Actually Rebuild a Binary Tree from Inorder and Postorder (Without Crying)

⚡ TL;DR

Given two arrays (inorder, postorder), you need to Frankenstein together the original binary tree. Beginners slice arrays like onions, but you should only slice if you enjoy pain and O(N²) speeds. Here’s the basic, gently-wrong idea you might see first:

// Please do not submit this to Leetcode
TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder.length == 0) return null;
    int rootVal = postorder[postorder.length - 1];
    TreeNode root = new TreeNode(rootVal);
    // Find root in inorder, split left/right, recurse... (slow)
    // ...
}

🧠 How Devs Usually Mess This Up

Here’s the greatest hits collection:

🔍 What’s Actually Going On

Pretend postorder is a disaster suitcase you packed at 3 am. You always throw the root on top (last in postorder). Find where that root appears in the inorder list—this magically splits the problem into left and right baggage (subtrees). BUT: Since you’re popping elements from the back of postorder, always build right subtree first or you end up with a left-handed chainsaw. That’s not just dangerous, it’s wrong.

🛠️ PseudoCode

• Build a value-to-index map from inorder.
  

  Map<Integer, Integer> idx = new HashMap<>();
  for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);

• Recurse from the last element in postorder, using indices (not new arrays, please).
• On each call: pick root value from postorder[postIdx], decrement postIdx.
• Find root’s index in inorder. First, build right subtree (from rootIdx+1 to end). Then, build left subtree (start to rootIdx-1).
• Return the new root node with wired-in left/right branches.

💻 The Code

// Binary tree node definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> inorderIdx = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIdx.put(inorder[i], i);
        }
        int[] postIdx = {postorder.length - 1};
        return build(inorder, postorder, 0, inorder.length - 1, postIdx, inorderIdx);
    }
     private TreeNode build(int[] inorder, int[] postorder, int inStart, int inEnd, int[] postIdx, Map<Integer, Integer> inorderIdx) {
        if (inStart > inEnd) return null;
        int rootVal = postorder[postIdx[0]--];
        TreeNode root = new TreeNode(rootVal);
        int idx = inorderIdx.get(rootVal);
        root.right = build(inorder, postorder, idx + 1, inEnd, postIdx, inorderIdx);
        root.left = build(inorder, postorder, inStart, idx - 1, postIdx, inorderIdx);
        return root;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Don’t build left first: Postorder demands right -> left -> root, or you get a botanical horror show.
• Index slips: Start/end math errors are probably responsible for 30% of unsolved tree problems. Check your ranges.
• No hashmap = sadness: Looking up inorder index with a for-loop means your tree grows slower than actual trees. Use the Map.
• Time: All operations are O(N) if you mind your indices. Yes, even if the interviewer makes a face.
• Space: O(N) for the hashmap and recursion stack. (Flattened trees and recursion limits not included.)

🧠 Interviewer Brain-Tattoo

If you build the left side first, the only thing you’ve constructed is an excuse not to pass the interview. Right subtree first!