105 · Construct Binary Tree from Preorder and Inorder

Preorder gives you the root; inorder tells you how much of what follows belongs to the left. The index map plus the arithmetic for the two sub-ranges is the entire problem — and it is always an off-by-one.

1 — The problem

Rebuild the tree from its preorder and inorder traversals, given distinct values. Two facts do all the work:

So the two traversals are complementary: preorder names the root, inorder sizes the halves. Either alone is ambiguous — which is exactly what LC 889 demonstrates, and why "preorder + postorder" does not determine a unique tree.

Finding the root's position by scanning inorder is O(n) per node and makes the whole thing O(n²). Build a value → index map once, up front, and every lookup is O(1).

2 — Two ranges, shrinking together

Follow the leftSize value. It is computed from inorder and then spent on preorder — that hand-off is the mechanism, and every index in lines 7 and 8 is derived from it.

2.1 Deriving the four indices, not memorising them

Write out the preorder range as three labelled pieces and every bound reads off directly:

And the inorder range splits at k: left is inL … k-1, right is k+1 … inR. Six bounds, all forced. The two that get written wrong most often:

• preL + leftSize as the left subtree's last index — not preL + leftSize - 1. The +1 for the root and the -1 for an inclusive bound cancel. Verify it on a one-node left subtree: leftSize = 1 should give the single index preL+1 … preL+1. It does.
• leftSize = k - inL — not k. Using k works at the root, where inL = 0, and fails everywhere else. This is the bug that passes the first sample and nothing after it.

2.2 The consumed-pointer variant

Because preorder is consumed strictly left to right, the preL parameter can be replaced by one shared cursor, leaving only the inorder range:

private int pre = 0;

private TreeNode build(int inL, int inR) {
    if (inL > inR) return null;
    int v = preorder[pre++];             // consume in preorder order
    int k = idx.get(v);
    TreeNode nd = new TreeNode(v);
    nd.left  = build(inL, k - 1);          // LEFT first — preorder demands it
    nd.right = build(k + 1, inR);
    return nd;
}

Two indices instead of four, and leftSize disappears entirely. The price is that the cursor is shared mutable state, so the recursion order becomes load-bearing: left must be built before right, because that is the order preorder stored them. LC 106 is the same idea with the cursor running backwards and the calls reversed — write them one after the other or they will fuse in memory.

3 — Complexity and edge cases

• Time O(n) with the index map, O(n²) if you scan inorder for each root. Space O(n) for the map plus O(h) for the recursion.
• Empty input: preL > preR on the first call returns null.
• Single node: leftSize = 0, both recursive calls hit the guard immediately.
• A straight line (every node has one child) is the worst case for recursion depth — O(n) stack — and the best test of the range arithmetic, because one side is always empty.
• Duplicate values break the approach outright: the index map becomes ambiguous and the tree is not uniquely determined. LeetCode guarantees distinct values; a follow-up asking about duplicates is asking you to notice that it is unanswerable.
• Common bug: passing k where k - inL is meant, as above.

4 — Reference implementation

private int[] pre;
private Map<Integer, Integer> idx = new HashMap<>();

public TreeNode buildTree(int[] preorder, int[] inorder) {
    pre = preorder;
    for (int i = 0; i < inorder.length; i++) idx.put(inorder[i], i);
    return build(0, preorder.length - 1, 0, inorder.length - 1);
}

private TreeNode build(int preL, int preR, int inL, int inR) {
    if (preL > preR) return null;
    int rootVal  = pre[preL];
    int k        = idx.get(rootVal);      // root's seat in inorder
    int leftSize = k - inL;               // how many nodes are to its left
    TreeNode nd = new TreeNode(rootVal);
    nd.left  = build(preL + 1, preL + leftSize, inL, k - 1);
    nd.right = build(preL + leftSize + 1, preR, k + 1, inR);
    return nd;
}