Construct Binary Tree from Preorder and Inorder

You are given two integer arrays, preorder and inorder, representing the preorder and inorder traversals of a binary tree. Your job is to reconstruct the original tree and return its root.

This is LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal, and it is one of the most important medium-difficulty tree problems. If you understand how to rebuild a tree from traversals, you truly understand what preorder and inorder mean. If you do not, this problem will teach you.

Why two traversals?

A single traversal is not enough to uniquely define a binary tree. Multiple different trees can produce the same preorder sequence. But if you have both preorder and inorder together, there is exactly one tree that matches. The two arrays give you complementary information: preorder tells you which node to process next, and inorder tells you which nodes belong on the left vs. right.

Here is the key insight that makes the whole algorithm click:

1. The first element of preorder is always the root of the current (sub)tree.
2. Find that root value in inorder. Everything to its left in inorder belongs to the left subtree. Everything to its right belongs to the right subtree.
3. The count of left-subtree elements tells you how to split preorder too.
4. Recurse on both halves.

That is the entire algorithm. Let's walk through it.

Step-by-step walkthrough

We will use preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7] to reconstruct this tree:

        3
       / \
      9   20
         /  \
       15    7

Each recursive call does the same thing: grab the root from preorder, find it in inorder, split, and recurse. The recursion bottoms out when a partition is empty, meaning there is no subtree on that side.

The code

Here is the clean implementation. The hashmap lookup for the root index in inorder is what brings the time down from O(n^2) to O(n).

def build_tree(preorder, inorder):
    # Map each value to its index in inorder for O(1) lookups
    inorder_index = {val: i for i, val in enumerate(inorder)}
    pre_iter = iter(preorder)

    def build(in_start, in_end):
        if in_start > in_end:
            return None

        root_val = next(pre_iter)
        root = TreeNode(root_val)

        # Find where root sits in inorder
        mid = inorder_index[root_val]

        # Build left subtree first (matches preorder's left-before-right order)
        root.left = build(in_start, mid - 1)
        # Then build right subtree
        root.right = build(mid + 1, in_end)

        return root

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

Let's break down why this works:

The iterator trick. Instead of slicing preorder into sub-arrays (which costs O(n) per slice), we use an iterator. Since preorder visits nodes in exactly the order we need to create them (root, then left subtree, then right subtree), we just call next() each time we need the next root. The iterator naturally advances through the array in the right order.

The hashmap. Without it, finding the root in inorder takes O(n) per call, giving O(n^2) total. The hashmap makes each lookup O(1).

The in_start and in_end bounds. These define which slice of inorder the current subtree corresponds to. When in_start > in_end, the slice is empty, meaning no subtree exists on that side.

Left before right. We must build the left subtree before the right subtree. This matches the order that preorder traversal visits nodes. If you swapped the two recursive calls, next(pre_iter) would give you the wrong value.

Dry run

Let's trace through every recursive call to make sure the logic is solid.

Call: build(0, 4) with preorder = [3, 9, 20, 15, 7]

• next(pre_iter) gives 3. Root is 3.
• inorder_index[3] is 1. So mid = 1.
• Left subtree: build(0, 0) (only index 0, which is value 9).
• Right subtree: build(2, 4) (indices 2 through 4: values 15, 20, 7).

Call: build(0, 0) (left subtree of 3)

• next(pre_iter) gives 9. Root is 9.
• inorder_index[9] is 0. So mid = 0.
• Left: build(0, -1) returns None (empty range).
• Right: build(1, 0) returns None (empty range).
• Node 9 is a leaf.

Call: build(2, 4) (right subtree of 3)

• next(pre_iter) gives 20. Root is 20.
• inorder_index[20] is 3. So mid = 3.
• Left: build(2, 2) (only index 2, value 15).
• Right: build(4, 4) (only index 4, value 7).

Call: build(2, 2) (left subtree of 20)

• next(pre_iter) gives 15. Leaf node.

Call: build(4, 4) (right subtree of 20)

• next(pre_iter) gives 7. Leaf node.

Every value consumed, every node placed. The tree is fully reconstructed.

Complexity analysis

Time is O(n). We visit each node exactly once. The hashmap gives O(1) lookups, and the iterator gives O(1) access to the next preorder value. No slicing, no searching.

Space is O(n). The hashmap stores n entries. The recursion stack goes as deep as the tree height, which is O(n) in the worst case (a completely skewed tree) and O(log n) for a balanced tree. The hashmap dominates.

Without the hashmap, time would be O(n^2) because each recursive call would need to scan inorder to find the root. That is the difference between a clean solution and a slow one.

Edge cases to watch for

• Empty arrays: if preorder and inorder are both empty, return None. The in_start > in_end base case handles this.
• Single node: both arrays have one element. The root is created, both recursive calls return None, and you get a single-node tree.
• Left-skewed tree: preorder is [1, 2, 3] and inorder is [3, 2, 1]. Every node only has a left child. The right subtree is always empty. Recursion depth is O(n).
• Right-skewed tree: preorder is [1, 2, 3] and inorder is [1, 2, 3]. Every node only has a right child. Same O(n) depth.
• Duplicate values: the problem guarantees no duplicates. If duplicates existed, you could not uniquely identify the root's position in inorder. The hashmap would also break because it maps each value to a single index.

The building blocks

This problem is built on one fundamental building block: tree construction from traversals (tree-construction-traversals).

The core pattern is: use one traversal to identify the root, use the other to determine what belongs on the left vs. right, then recurse. This same pattern applies to constructing a tree from postorder and inorder (LeetCode 106), where the only difference is that the root comes from the end of postorder instead of the beginning.

# The skeleton for constructing from preorder + inorder:
def build(in_start, in_end):
    if in_start > in_end:
        return None
    root_val = next(pre_iter)        # root from preorder
    mid = inorder_index[root_val]    # find split point in inorder
    node = TreeNode(root_val)
    node.left = build(in_start, mid - 1)   # left partition
    node.right = build(mid + 1, in_end)    # right partition
    return node

The key ideas that transfer to other tree problems:

• Preorder's first element is always the root of the current subtree. This is true by definition of preorder traversal.
• Inorder splits left from right. Once you find the root in inorder, the partition is immediate.
• A hashmap eliminates repeated linear scans. This optimization pattern shows up in many problems where you need to find an element's position repeatedly.
• An iterator avoids array slicing. Instead of creating new sub-arrays (O(n) per call), you advance a pointer through the original array.

From understanding to recall

You just traced through every recursive call and saw exactly how preorder gives you roots and inorder gives you boundaries. The algorithm is elegant once you see it. But will you remember it in two weeks?

The tricky parts are subtle. You need to remember that left must be built before right (to match preorder's ordering). You need to remember the hashmap optimization. You need to remember that in_start > in_end is the base case, not in_start == in_end.

These details are easy to forget and hard to re-derive under pressure. Spaced repetition fixes that. You type the solution from scratch at increasing intervals. The first few times, you might forget the iterator trick or mix up the recursive call order. After a few reps, the pattern is automatic.

The tree-construction-traversals building block also directly helps with LeetCode 106 (Construct Binary Tree from Inorder and Postorder). The only change is where you pull the root from. If you have drilled the preorder version, the postorder version takes minutes instead of hours.

Related posts

• Trees: Binary Trees, BSTs, and Traversals - Covers traversal orders (preorder, inorder, postorder) in depth, essential background for understanding why this algorithm works
• Validate BST: Range Checking vs Inorder - Another problem where inorder traversal properties are central to the solution, good practice for thinking about tree ordering