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!)

🧠 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

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

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.

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.

💻 The Code

// Tree node definition
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private Map&lt;Integer, Integer&gt; map;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap&lt;&gt;();
        for (int i = 0; i &lt; 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 &gt; preR || inL &gt; 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.