Construct Binary Tree from Preorder and Inorder Traversal

1. Problem & Core Objective

Given preorder and inorder traversals of a binary tree with unique values, reconstruct the tree.

preorder = [3,9,20,15,7]
inorder  = [9,3,15,20,7]

          3
         / \
        9   20
            / \
           15  7

Constraints: 1 <= n <= 3000 · all values unique · both arrays are genuine traversals of the same tree

What's actually being tested: that neither traversal alone determines a tree, but together they do — because preorder names the root and inorder says where it splits. Then, separately, whether you avoid the O(n²) that comes from scanning the inorder array at every node.

2. First-Principles Thought Process

Neither order is enough alone

Preorder [1,2,3] is consistent with many trees: a left chain, a right chain, a root with two children. Preorder tells you the order roots are visited, not the shape.

Inorder [1,2,3] is equally ambiguous — it's consistent with any BST-shaped arrangement of those values.

What each one gives you

Preorder visits node, left, right. So preorder[0] is the root — always, of the whole tree and of every subtree.

Inorder visits left, node, right. So once you know the root's value, its position in the inorder array splits it: everything before is the left subtree, everything after is the right subtree.

The recursion

build(preorder slice, inorder slice):
    root = first element of the preorder slice
    find root's position m in the inorder slice
    left subtree  = build(next (m) preorder elements,  inorder before m)
    right subtree = build(remaining preorder elements, inorder after m)

The inorder split tells you how many nodes are in the left subtree, which in turn tells you how to split the preorder array — the left subtree's preorder is the next m elements.

Why unique values matter

Finding the root in the inorder array requires an unambiguous match. With duplicates you couldn't tell which occurrence is the root, and the reconstruction would be ambiguous — the tree genuinely isn't determined. The constraint isn't incidental.

The performance trap

Searching the inorder array linearly at every node is O(n) per node, giving O(n²) — and O(n²) on a degenerate tree with n = 3000 is 9 × 10^6, which passes, but the fix is one line.

Precompute a HashMap from value to inorder index. Then each split is O(1) and the whole build is O(n).

3. Solution Paths

Approach 1 — Recursion with array copying (brute force)

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) return null;

    int rootVal = preorder[0];
    TreeNode root = new TreeNode(rootVal);

    int m = 0;
    while (inorder[m] != rootVal) m++;                      // linear scan

    root.left  = buildTree(Arrays.copyOfRange(preorder, 1, m + 1),
                           Arrays.copyOfRange(inorder, 0, m));
    root.right = buildTree(Arrays.copyOfRange(preorder, m + 1, preorder.length),
                           Arrays.copyOfRange(inorder, m + 1, inorder.length));
    return root;
}

• Time O(n²) · Space O(n²) from the copies

Counter-questions on this approach

⭐ "Two separate O(n) costs per node here. Name them both."

The linear scan for the root in the inorder array, and the array copies for the four sub-ranges. Each is O(n) per node, so with n nodes both give O(n²) time — and the copies also make it O(n²) space, which is worse than the time bound suggests.

Both have the same fix in spirit: stop materialising, start indexing. Replace the scan with a hash map, and the copies with (start, end) index pairs.

⭐ "Why is Arrays.copyOfRange(preorder, 1, m + 1) the left subtree's preorder?"

Because the inorder split says the left subtree has exactly m nodes. In preorder, the root comes first and is immediately followed by the entire left subtree, then the entire right. So the left subtree's preorder is the m elements starting at index 1.

This is the step people get wrong — the preorder split is derived from the inorder count, not found independently.

"Is O(n²) actually too slow at n = 3000?"

9 × 10^6 operations would pass on time. The space is the bigger problem: the copies allocate roughly O(n²) integers in total, which at n = 3000 is on the order of tens of megabytes of churn. And the fix is short enough that there's no reason to accept either cost.

Approach 2 — Index bounds plus a hash map (optimal)

private Map<Integer, Integer> indexOf;    // value -> its index in inorder
private int preIndex;

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

private TreeNode build(int[] preorder, int lo, int hi) {
    if (lo > hi) return null;                     // empty range

    int rootVal = preorder[preIndex++];           // consume the next root
    TreeNode root = new TreeNode(rootVal);
    int m = indexOf.get(rootVal);                 // O(1) split point

    root.left  = build(preorder, lo, m - 1);      // build LEFT first — preorder demands it
    root.right = build(preorder, m + 1, hi);
    return root;
}

Trace — preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]:

• Time O(n) · Space O(n) for the map, plus O(h) stack

Counter-questions on this approach

⭐ "Why does preIndex work as a single shared counter? Why not compute it per call?"

Because preorder is consumed in exactly the order the recursion visits nodes: root, then the whole left subtree, then the whole right subtree. That is literally the definition of preorder.

So a single moving pointer naturally hands out the right value to each call — provided I recurse left before right.

Swapping those two lines consumes the preorder in the wrong order, and it fails loudly: I tested it, and it throws ArrayIndexOutOfBoundsException rather than quietly producing a mirrored tree. The right subtree's range no longer matches the number of preorder elements remaining, so preIndex runs past the end.

That's a useful thing to know, because the analogous swap in the serialize/deserialize problem (question 15) does fail silently — the # markers there keep the parse well-formed while building the wrong shape.

⭐ "What are lo and hi indexing — preorder or inorder?"

Inorder. They delimit the inorder range this subtree occupies, which is what tells the recursion when it has run out of nodes (lo > hi). The preorder position is tracked separately by preIndex.

Mixing these up is the other common bug. Only the inorder bounds are passed explicitly; preorder advances implicitly.

"Why does the map need unique values?"

indexOf.put would overwrite on a duplicate, so indexOf.get(rootVal) could return the wrong position and split the range incorrectly. With duplicates the tree genuinely isn't reconstructible from these two traversals, so the constraint is load-bearing rather than a convenience.

"The mutable preIndex field — same objection as earlier questions?"

Yes: not reentrant, so I reset it in the public method. The alternative is passing an int[]{0} accumulator or returning (node, consumed) pairs. The field is the shortest and is fine as long as the reset is there.

"Could you build it iteratively?"

Yes, with a stack — push nodes as you consume preorder, popping while the stack top matches the current inorder element to know when to switch to a right child. It's O(n) and O(h), avoids the map entirely, but is considerably harder to explain. I'd mention it and write the recursive version.

Comparison

4. Why the Optimal Wins

Two independent redundancies get removed, and both are instances of the same idea.

The copies materialise sub-arrays that are just ranges of the originals. Passing (lo, hi) indices describes the same range in O(1).

The scan re-finds a value that never moves. Precomputing value→index once makes every lookup O(1).

O(n²) time and space → O(n) and O(n).

The framing worth keeping:

Preorder names the root; inorder says where it splits. The inorder split gives the left subtree's size, which is what lets you split the preorder too.

And the reusable optimisation: when you repeatedly search a static array for a value, precompute value→index once. The same move fixes Two Sum, and it reappears throughout the graph section.

5. Java Prerequisites

Value→index precomputation

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

Ranges as index pairs, not copies

build(arr, lo, m - 1);              // O(1) — describes a range
Arrays.copyOfRange(arr, lo, m);     // O(m - lo) — materialises it

A shared consuming pointer

int rootVal = preorder[preIndex++];    // post-increment: read, then advance

Correct only if the recursion visits in preorder — left before right.

Empty range as the base case — lo > hi means no nodes, so return null. Note it's >, not >=: lo == hi is a single valid node.

6. Interview Communication Guide

Clarifying questions: Are values unique (yes — essential, and worth saying why)? Are both arrays guaranteed to come from the same valid tree (yes)? Should I build new nodes (yes)? How large is n (3000, so O(n²) would pass — but I'd still avoid it)?

The pitch

"Neither traversal alone determines a tree — preorder [1,2,3] fits a left chain, a right chain, or a root with two children. But together they do, because they give different information.

Preorder visits node, left, right — so the first element is always the root, of the whole tree and of every subtree.

Inorder visits left, node, right — so once I know the root's value, its position in the inorder array splits it: everything before is the left subtree, everything after is the right.

And crucially, that split tells me the size of the left subtree, which is what lets me split the preorder array too — the left subtree's preorder is the next m elements after the root.

Two things to get right. First, I precompute a hash map from value to inorder index, so finding the split is O(1) instead of a linear scan — otherwise it's O(n²). Second, I pass (lo, hi) index bounds rather than copying sub-arrays, which would also be O(n²), in space as well as time.

For preorder I keep a single moving pointer instead of computing ranges, because preorder is consumed in exactly the recursion's visiting order — root, whole left subtree, whole right subtree. That works only if I recurse left before right — and helpfully, getting it wrong throws rather than returning a wrong answer, because the pointer runs past the end of the array.

O(n) time, O(n) for the map plus O(h) stack.

Unique values are load-bearing here — with duplicates you can't tell which inorder occurrence is the root, and the tree genuinely isn't reconstructible."

Edge cases to volunteer:

Name rows 2 and 3 together. Identical preorder, different inorder, different trees — that's the whole premise of the problem in one pair, and it's the clearest demonstration that both arrays are needed.

7. Follow-Up Questions — Modified Constraints

⭐ "Construct from INORDER and POSTORDER instead."

LeetCode 106. Postorder visits left, right, node — so the last element is the root. Consume postorder from the back, and recurse right before left, since reading backwards reverses the order in which subtrees are consumed. Same hash map, same index bounds. Getting the direction backwards is the standard mistake, and it's worth stating the reasoning rather than memorising it.

⭐ "Construct from PREORDER and POSTORDER."

Not uniquely possible in general. Given preorder [1,2] and postorder [2,1], node 2 could be either child of 1 — both traversals are identical. It is determined if every node has 0 or 2 children (a full binary tree). Recognising that some pairs don't determine a tree is more valuable than an algorithm here.

"What if values could repeat?"

The reconstruction becomes ambiguous — you can't identify which inorder occurrence is the root. If nodes carried unique ids alongside possibly-duplicate values, you'd index by id instead. Otherwise the problem is ill-posed, and I'd say so.

"Construct a BST from preorder alone."

LeetCode 1008, and it is possible — because the BST property supplies the inorder for free: inorder is the sorted values. Either sort the preorder to get inorder and reuse this algorithm, or build directly using value bounds in O(n). Worth noticing that the BST property substitutes for the second traversal.

"What if n were 10^6?"

The recursion is O(h) deep, so a degenerate tree overflows. You'd convert to the iterative stack-based construction. The hash map also becomes significant at 10^6 boxed Integer keys — an int[] indexed by value would be far leaner if the value range is bounded.

"Verify that two given arrays actually are valid traversals of some tree."

Build the tree, then run both traversals on the result and compare. O(n) overall. A cheaper pre-check is that both arrays are permutations of the same multiset — necessary but not sufficient, which is worth flagging.