LeetCode 105 – Construct Binary Tree from Preorder and Inorder Traversal

This is the problem that makes traversal orders click. Neither preorder nor inorder alone determines a tree — many different trees share each — but together they do, and the reason is a single sentence you should be able to say before writing anything.

The problem

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

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

        3
       / \        preorder: root, left subtree, right subtree
      9   20      inorder:  left subtree, root, right subtree
         /  \
        15   7

"Distinct" is load-bearing and worth checking aloud. With duplicates the reconstruction is ambiguous, because you could not tell which occurrence of the root value in the inorder array is the root.

The two facts

preorder = [ROOT] [ ... left ... ] [ ... right ... ]
inorder  = [ ... left ... ] [ROOT] [ ... right ... ]

Preorder tells you the root. Inorder tells you the split. That is the whole algorithm. Take preorder[0] as the root, find it in the inorder array, and everything to its left is the left subtree while everything to its right is the right subtree. Recurse on both halves.

root = preorder[0] = 3
inorder: [9] 3 [15, 20, 7]
          ^      ^
     left subtree   right subtree, 3 nodes

so preorder splits as: 3 | [9] | [20, 15, 7]
                             ^      ^
                        1 node   the remaining 3

The sizes come from the inorder split and then tell you where to cut the preorder array. That cross-reference is the mechanical heart of the problem.

Two things that make it O(n)

Do not search the inorder array. Scanning for the root at every node is O(n) per call and O(n²) overall — quadratic on a degenerate tree, which is exactly the input designed to catch it. Build a value → index map once up front and each lookup becomes O(1). This is the single change that matters.

Do not slice arrays. Passing preorder[1:mid+1] at every level copies O(n) elements per call and reintroduces the quadratic behaviour you just removed — quietly, since the code still looks linear. Pass index ranges instead.

The consumed-so-far pointer

The neat formulation keeps a single moving index into the preorder array. Because preorder visits root, then all of the left subtree, then the right, building the left subtree first leaves that index sitting exactly at the start of the right subtree:

build(left, right):
    root = preorder[preIndex++]
    mid  = indexOf(root) in inorder
    root.left  = build(left, mid - 1)      <- MUST be first
    root.right = build(mid + 1, right)

Swap those two lines and the answer is wrong, with no error — the right subtree consumes the preorder values that belonged to the left. The ordering is not stylistic; it is the invariant.

Java

class Solution {
    private int preIndex;
    private Map<Integer, Integer> inorderIndex;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // Reset both: without this, a second call on the same object starts
        // partway through the preorder array and returns nonsense.
        preIndex = 0;
        inorderIndex = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndex.put(inorder[i], i);      // O(1) lookups instead of a scan
        }

        return build(preorder, 0, inorder.length - 1);
    }

    /** Builds the subtree occupying inorder[left..right]. */
    private TreeNode build(int[] preorder, int left, int right) {
        if (left > right) return null;

        int rootValue = preorder[preIndex++];
        TreeNode root = new TreeNode(rootValue);
        int mid = inorderIndex.get(rootValue);

        root.left = build(preorder, left, mid - 1);    // left FIRST -- preIndex depends on it
        root.right = build(preorder, mid + 1, right);

        return root;
    }
}

The reset is not defensive padding. Instance state that survives between calls is a real bug class — the same one that made an earlier solution in this track return a stale answer on its second invocation — and an interviewer who calls your method twice will find it.

If you would rather have no mutable state at all, the preorder start index can be computed instead of tracked: the left subtree has mid - left nodes, so the right subtree's preorder begins at preStart + 1 + (mid - left). Four parameters instead of a field. Both are fine; say which trade you are making.

Python

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> TreeNode:
        index_of = {value: i for i, value in enumerate(inorder)}
        self.pre_index = 0

        def build(left: int, right: int) -> TreeNode:
            if left > right:
                return None

            root_value = preorder[self.pre_index]
            self.pre_index += 1

            root = TreeNode(root_value)
            mid = index_of[root_value]

            root.left = build(left, mid - 1)      # left first: pre_index advances in order
            root.right = build(mid + 1, right)

            return root

        return build(0, len(inorder) - 1)

self.pre_index is reassigned at the start of every call, so the reuse problem does not arise. A plain local would not work — the nested function would need nonlocal, which is the same mechanism Diameter of Binary Tree needs and the same thing that silently breaks when it is forgotten.

Complexity

Each node is created once and each preorder value consumed once. The map is O(n) space and buys a factor of n in time — the standard trade, and worth naming as such.

Which pairs of traversals are enough?

Inorder is what supplies the split, so a pair without it cannot say which side a lone child sits on. Knowing that third row is the difference between having memorised the algorithm and having understood it.

The pattern

Construct from Inorder and Postorder (106) is the mirror: consume postorder from the back, and build the right subtree first. Construct from Preorder and Postorder (889) returns any valid tree, precisely because the answer is not unique. Serialize and Deserialize (297) is the general version, and it works with a single traversal only because it writes the nulls down too — which is what removes the ambiguity.

What the interviewer is checking

• That you state the two facts: preorder gives the root, inorder gives the split.
• The hash map, and that you say why scanning is O(n²).
• Index ranges instead of array slices.
• Left subtree built before right, and why swapping them silently breaks it.
• That values must be distinct, and what breaks if they are not.
• Empty input and a single node.
• That instance state is reset, so a second call works.
• Bonus: that preorder + postorder is not enough.