105. Construct Binary Tree from Preorder and Inorder Traversal

Rebuilding a tree from two of its traversals looks like it should need bookkeeping gymnastics, but it’s really one observation applied recursively. It’s a favorite in the binary tree pattern set precisely because it forces you to say out loud what preorder and inorder each tell you — and once you can, the code writes itself.

The problem

You’re given two arrays: the preorder traversal of a binary tree and its inorder traversal, both over the same set of unique values. Rebuild the actual tree and return its root. (Full statement on LeetCode.)

Say preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]. The answer is a tree rooted at 3, with 9 on the left and a 20-rooted subtree (children 15 and 7) on the right.

Intuition: preorder names the root, inorder cuts it in half

Two facts do all the work here.

• Preorder visits root first. So preorder[0] is always the root of whatever subtree you’re currently building. Consume it and the next unused preorder value becomes the root of the next subtree — as long as you build left before right.
• Inorder splits around the root. Everything to the left of the root’s position in inorder is its left subtree; everything to the right is its right subtree.

Put them together. Take 3 from preorder — that’s the root. Find 3 in inorder at index 1, so [9] is the left subtree and [15, 20, 7] is the right. Recurse on each side, and the next preorder value (9) roots the left, then 20 roots the right. The one detail that keeps this $O(n)$ is finding the root’s inorder position without scanning: pre-hash every value to its index, so each lookup is $O(1)$ and the whole build is:

$T(n) = O(n)$

Solution

The recursion carries a [left, right] window into the inorder array — the slice of values that belong to the current subtree. A shared preIdx walks the preorder array forward, handing out roots in exactly the order preorder recorded them.

import java.util.HashMap;
import java.util.Map;

public class Solution {

    private int preIdx = 0;
    private Map<Integer, Integer> inorderIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        preIdx = 0;                 // reset so a second call starts clean
        inorderIndex.clear();
        // value -> its position in inorder, for O(1) root splits
        for (int i = 0; i < inorder.length; i++) {
            inorderIndex.put(inorder[i], i);
        }
        return build(preorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) return null;   // empty inorder slice -> no node

        int rootVal = preorder[preIdx++];       // preorder hands out roots in order
        TreeNode root = new TreeNode(rootVal);

        int mid = inorderIndex.get(rootVal);     // where the root sits in inorder
        root.left = build(preorder, left, mid - 1);   // values before it
        root.right = build(preorder, mid + 1, right); // values after it
        return root;
    }
}

The ordering of those two recursive calls is load-bearing: preIdx must advance through the entire left subtree before it reaches the right one, which is exactly what preorder guarantees.

Complexity

	Time	Space
Recursive build	$O(n)$	$O(n)$

Every node is created once and its inorder index is found in $O(1)$. The space is the hash map plus the recursion stack, which is $O(n)$ in the worst case of a degenerate, list-shaped tree.

In an interview

Start by stating the two invariants — “preorder gives me the root, inorder splits into left and right around it” — because that sentence is the solution and it’s what’s being graded. Then flag the optimization out loud: a naive indexOf on inorder inside the recursion makes it $O(n^2)$, so you pre-map values to indices to keep it linear.

The trap is the recursion order. If you build the right subtree before the left, preIdx skips ahead and the whole tree comes out scrambled — mention that you build left first on purpose. This also quietly relies on values being unique; ask about duplicates, since without uniqueness the inorder split is ambiguous and the approach breaks.

For more on tree reconstruction and traversal, this sits in the binary tree pattern hub. It pairs naturally with Serialize and Deserialize Binary Tree, which is the same “rebuild from a linear encoding” idea, and with Binary Tree Level Order Traversal if you want to see how a different traversal order changes what you can recover.

References

• LeetCode 105 — Construct Binary Tree from Preorder and Inorder Traversal