A config service crashed and wrote two dumps of the same unique-key tree: a preorder dump and an inorder dump. Rebuild the live tree so the next request can walk it. The intern version, for each new root, scanned the remaining inorder window until the value showed up, then split. The rebuilt catalog looked right. A few thousand unique keys still came back, but every split paid a linear scan.

The next unused preorder value is the root. Its position in inorder is the cut between left and right. The binary tree post owns preorder and inorder as layout walks. Here we only care about using those two arrays as a split: first unused preorder value names the node; everything left of that value in inorder is the left subtree, everything right is the right subtree.

The problem

Given a preorder array and an inorder array of the same binary tree, rebuild the tree and return the root. Values are unique. Empty arrays return null. A single value is a one-node tree.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Walk preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]. 3 is the first unused preorder value, so it is the root. In inorder, 9 sits left of 3 and 15, 20, 7 sit right. The left window is size 1, so the next preorder value 9 is that leaf. The right window starts at the next unused preorder value 20. Split inorder at 20: 15 left, 7 right.

      3
     / \
    9  20
      /  \
     15   7

Note: Unique values are the spec, not a courtesy. A duplicate would make the inorder cut ambiguous — two candidate splits, one tree.

Nested scan of inorder for each root is the honest brute force

Take pre[preLo] as the root. Walk the inorder window until that value appears; that index is mid. The left subtree size is mid - inLo. Recurse on the matching preorder and inorder slices. Correct. Each root pays a scan.

TreeNode buildTreeBrute(int[] preorder, int[] inorder) {
    return buildBrute(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}

TreeNode buildBrute(int[] pre, int preLo, int preHi, int[] in, int inLo, int inHi) {
    if (preLo > preHi) {
        return null;
    }
    int rootVal = pre[preLo];
    TreeNode root = new TreeNode(rootVal);
    int mid = inLo;
    while (in[mid] != rootVal) {
        mid++;
    }
    int leftSize = mid - inLo;
    root.left = buildBrute(pre, preLo + 1, preLo + leftSize, in, inLo, mid - 1);
    root.right = buildBrute(pre, preLo + leftSize + 1, preHi, in, mid + 1, inHi);
    return root;
}

A spine where every root sits at the far end of its inorder window is about 1 + 2 + … + n comparisons. That is the quadratic you shipped for a question that only needed the cut index.

Hash inorder value to index, then split in O(1)

Build a map from each inorder value to its index once. Keep a preorder cursor that only moves forward: consume the next value, look up mid, recurse on (inLo, mid - 1) then (mid + 1, inHi). Preorder already lists root, then the left subtree, then the right subtree, so the cursor is enough — you do not need a second pair of preorder bounds.

inIndex: 9→0, 3→1, 15→2, 20→3, 7→4
preIdx starts at 0

consume 3  mid=1  left window [0,0]  right window [2,4]
  consume 9  mid=0  both child windows empty  → leaf 9
  consume 20 mid=3  left [2,2]  right [4,4]
    consume 15 mid=2  → leaf 15
    consume 7  mid=4  → leaf 7

The Java is that walk. Left before right matches preorder, so preIdx is a one-slot array (Java has no pass-by-ref int).

TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inIndex = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inIndex.put(inorder[i], i);
    }
    return build(preorder, new int[] {0}, 0, inorder.length - 1, inIndex);
}

TreeNode build(int[] pre, int[] preIdx, int inLo, int inHi, Map<Integer, Integer> inIndex) {
    if (inLo > inHi) {
        return null;
    }
    int rootVal = pre[preIdx[0]++];
    TreeNode root = new TreeNode(rootVal);
    int mid = inIndex.get(rootVal);
    root.left = build(pre, preIdx, inLo, mid - 1, inIndex);
    root.right = build(pre, preIdx, mid + 1, inHi, inIndex);
    return root;
}

Time is O(n) — one map fill, then each value is consumed once from preorder and looked up once. Space is O(n) for the map, plus O(h) frames. Copying Arrays.copyOfRange at every split is another quadratic; the bounds are the window, not a new array.

Build left before right. Swap those two recursive calls and the preorder cursor feeds the right subtree the left subtree’s values. The inorder bounds would still look plausible; the shape would be wrong.

Empty arrays: inLo > inHi on the first call (0, -1), return null. One node: consume it, both child windows empty.

What interviewers usually poke next

  • Postorder + inorder. Sibling idea: the last unused postorder value is the root, and you build right before left so the cursor still matches the dump. Same map, opposite child order. Different prompt.
  • Preorder + postorder. Not the same trick. Without extra shape constraints (every node has 0 or 2 children) the split is not unique.
  • Serialize / deserialize. You choose an encoding and must round-trip nulls so the shape survives. These two arrays are given; they are not a codec you invent. Serialize is that contract.
  • Duplicates allowed. Refuse the map-as-cut unless they define a policy. This problem does not.

You are done with this problem when you can rebuild 3 / 9, 20 / 15, 7 from those two arrays out loud, name the quadratic scan, and say why serialize is a different contract.