The O(n) Club: Preorder-Inorder Tree Rebuilds — Actually Fun, Actually Linear

The O(n) Club: Preorder-Inorder Tree Rebuilds — Actually Fun, Actually Linear

⚡ TL;DR

Want to turn two scrambled traversals back into a perfectly good binary tree? Pick each root from preorder, split your world using inorder, and never manually scan for indices like some 1997 C intern. (HashMaps, people!)

// The "please don't ever actually ship this" brute force:
TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null;
    int rootVal = preorder[0];
    // Scan inorder to find where to split
    int rootIdx = -1;
    for (int i = 0; i < inorder.length; i++) {
        if (inorder[i] == rootVal) { rootIdx = i; break; }
    }
    // Now recursively handle left/right slices
    // ... (about as efficient as a horse on a skateboard)
}
// Don't do this. See below for modern wizardry.

🧠 How Devs Usually Mess This Up

If you like visiting the land of infinite bugs:

🔍 What’s Actually Going On

Preorder is basically a bossy dispatcher, always telling you the next root. Inorder is your map, showing where to draw the fence: everything left is a left subtree, everything right goes to the right. This is divide and conquer with attitude. Using a HashMap for quick lookups means you get all this drama without runtime angst.

🛠️ PseudoCode

• Build a value-to-index HashMap from inorder for O(1) splits:

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

  Why? If you don’t, you’ll spend all day searching.
• Recursively build the tree via index bounds (no array slicing):

  TreeNode helper(int preLeft, int preRight, int inLeft, int inRight)

  Tip: Keep explicit start/end pointers — cutting actual arrays is for people who hate RAM.
• Each call does:
  • Root is preorder[preLeft]
  • Find the root’s index in inorder via HashMap
  • Compute left size = index – inLeft
  • Recursively build left and right subtrees

💻 The Code

// Tree node definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 class Solution {
    private Map<Integer, Integer> map;
     public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
     private TreeNode helper(int[] preorder, int preL, int preR, int inL, int inR) {
        if (preL > preR || inL > inR) return null;
        int rootVal = preorder[preL];
        int idx = map.get(rootVal);
        int leftSize = idx - inL;
        TreeNode root = new TreeNode(rootVal);
        root.left = helper(preorder, preL + 1, preL + leftSize, inL, idx - 1);
        root.right = helper(preorder, preL + leftSize + 1, preR, idx + 1, inR);
        return root;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Watch those indices! One slip and you build a Schrödinger’s tree: both alive and broken.
• Duplicate values? The algorithm politely throws up its hands (doesn’t work!).
• HashMap is not optional. Without it, O(n²) calls will ruin your Big O cred and your mood.
• Expect O(n) time and space. Unless you write for a living, this is as good as it gets.

🧠 Interviewer Brain-Tattoo

Give me preorder and inorder and I will build your tree — or at least never waste time brute-forcing like it’s Y2K again.