Construct Binary Tree from Preorder and Inorder Traversal

The trap in this problem is stopping at “preorder gives the root.” That identifies one node, but not the boundaries of its children. The real solution is to let inorder define the split and let subtree sizes place those pieces correctly in preorder.

Read the traversal contract first

You receive two valid traversals of the same binary tree:

• Preorder: root, left subtree, right subtree
• Inorder: left subtree, root, right subtree

The values are unique, both arrays have the same length, and every value appears in both arrays. You must construct and return the root of the tree, not return another traversal.

Use the canonical example:

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

The first preorder value is 3, so 3 must be the root. In inorder, 3 appears between [9] and [15, 20, 7]. Therefore:

        3
       / \
      9   20
         /  \
        15   7

That structure is the entire problem in miniature:

1. Read the current root from preorder.
2. Find that root in inorder.
3. Everything before it belongs to the left subtree.
4. Everything after it belongs to the right subtree.
5. Repeat for both intervals.

The implementation challenge is keeping the preorder and inorder segments aligned without repeatedly copying or scanning arrays.

The key split: root in preorder, boundary in inorder

For any subtree, the first value in its preorder segment is its root.

Suppose a subtree uses this inorder interval:

[9, 3, 15, 20, 7]

Its root is 3. The index of 3 divides the interval:

left subtree  | root | right subtree
[9]           |  3   | [15, 20, 7]

The left subtree contains one node. That fact determines the preorder layout:

root | left subtree | right subtree
  3  |      9       |   20, 15, 7

The right subtree starts after:

• the current root: 1 value
• all nodes in the left subtree: left_size values

So if the current subtree starts at preorder index pre_start, the right subtree starts at:

pre_start + 1 + left_size

For the running example:

Subtree	Root	Inorder interval	Left size	Right preorder start
Entire tree	3	[9, 3, 15, 20, 7]	1	0 + 1 + 1 = 2
Right subtree	20	[15, 20, 7]	1	2 + 1 + 1 = 4

The important point is that the inorder index is a boundary, not a preorder offset. Mixing those two coordinate systems causes most off-by-one bugs.

Start with the brute-force version

A straightforward recursive solution can use inclusive inorder bounds:

build(pre_start, in_left, in_right)

At each call:

1. Read preorder[pre_start] as the root.
2. Scan inorder[in_left:in_right + 1] to find that root.
3. Recursively build the left interval.
4. Recursively build the right interval.

This version is useful because it exposes the structure clearly. Its bottleneck is the scan. In a skewed tree, the current subtree can contain almost every remaining node, and the next subtree can contain almost every remaining node again. The repeated scans add up to:

n + (n - 1) + (n - 2) + ... + 1 = O(n²)

The optimization is precise: build a value-to-index map for inorder once.

inorder_index = {value: index for index, value in enumerate(inorder)}

Then each root lookup is average-case O(1). Because values are unique, one index is enough for every value.

Define the recursive state and invariant

I prefer a helper with this state:

build(pre_start, in_start, size)

Its arguments mean:

• pre_start: first index of this subtree in preorder
• in_start: first index of this subtree in inorder
• size: number of nodes in this subtree

This representation avoids carrying two inclusive endpoints and makes the subtree size explicit.

The invariant

build(pre_start, in_start, size) returns the tree represented by the next size preorder values beginning at pre_start and the next size inorder values beginning at in_start.

That sentence is more valuable than memorizing the final formulas. It tells you what every recursive call must preserve.

For a nonempty subtree:

root_value = preorder[pre_start]
root_inorder_index = inorder_index[root_value]
left_size = root_inorder_index - in_start

Why does that subtraction work? The root is at root_inorder_index, and the subtree's inorder segment starts at in_start. Every value between those positions belongs to the left subtree.

Now derive the child states.

Left subtree

The left subtree:

• starts immediately after the root in preorder
• starts at in_start in inorder
• contains left_size nodes

build(pre_start + 1, in_start, left_size)

Right subtree

The right subtree:

• starts after the root and all left-subtree nodes in preorder
• starts immediately after the root in inorder
• contains size - 1 - left_size nodes

build(
    pre_start + 1 + left_size,
    root_inorder_index + 1,
    size - 1 - left_size
)

The base case is size == 0: there is no subtree, so return None.

This is divide and conquer with a clean contract. We split one valid subtree description into two smaller valid subtree descriptions, then attach their returned roots to the current root.

Why the construction is correct

The proof follows directly from the traversal definitions and the invariant.

Root correctness

In preorder, the first value of any subtree is its root. Therefore preorder[pre_start] is the correct root value for the current recursive call.

Partition correctness

In inorder, values before the root belong to the left subtree, and values after the root belong to the right subtree. The map gives the root's exact position, so:

left_size = root_inorder_index - in_start

is the number of left-subtree nodes.

Preorder alignment correctness

After the root, preorder lists the entire left subtree before listing any right-subtree node. Therefore:

• the left subtree begins at pre_start + 1
• the right subtree begins after 1 + left_size values

That gives the right start:

pre_start + 1 + left_size

Inductive conclusion

The recursive calls receive exactly the preorder and inorder segments belonging to their respective subtrees. Assuming the calls correctly construct smaller subtrees, attaching those results to the current root produces the required current subtree.

The recursion bottoms out when the segment has size zero. Since the input is guaranteed to contain valid matching traversals, the core solution does not need malformed-input handling.

Dry-run the index movement

Start with:

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

The inorder index map is:

{
    9: 0,
    3: 1,
    15: 2,
    20: 3,
    7: 4
}

First call

build(pre_start=0, in_start=0, size=5)

• Root: preorder[0] = 3
• Root index in inorder: 1
• Left size: 1 - 0 = 1
• Right size: 5 - 1 - 1 = 3

Recursive calls:

left:  build(pre_start=1, in_start=0, size=1)
right: build(pre_start=2, in_start=2, size=3)

The right preorder start is 2, not 1, because index 1 is occupied by the one-node left subtree.

Left call

build(pre_start=1, in_start=0, size=1)

• Root: preorder[1] = 9
• Inorder position: 0
• Left size: 0

Both children have size zero, so this creates the leaf 9.

Right call

build(pre_start=2, in_start=2, size=3)

• Root: preorder[2] = 20
• Inorder position: 3
• Left size: 3 - 2 = 1

Recursive calls:

left:  build(pre_start=3, in_start=2, size=1)  # node 15
right: build(pre_start=4, in_start=4, size=1)  # node 7

The final tree is therefore:

        3
       / \
      9   20
         /  \
        15   7

A useful skewed case is:

preorder = [1, 2, 3]
inorder  = [3, 2, 1]

Every root appears at the right edge of its inorder interval, so every left_size is size - 1 and every right subtree has size zero. The recursion follows only left children.

For a right-skewed tree:

preorder = [1, 2, 3]
inorder  = [1, 2, 3]

Every root appears at the left edge, so every left subtree has size zero and recursion follows only right children.

These cases are valuable because they expose both boundary behavior and maximum recursion depth.

Implement the Python solution cleanly

The platform usually provides TreeNode. The helper below keeps the preorder and inorder coordinates visible and avoids slicing:

from typing import List, Optional


class Solution:
    def buildTree(
        self,
        preorder: List[int],
        inorder: List[int],
    ) -> Optional["TreeNode"]:
        inorder_index = {
            value: index
            for index, value in enumerate(inorder)
        }

        def build(pre_start: int, in_start: int, size: int):
            if size == 0:
                return None

            root_value = preorder[pre_start]
            root_inorder_index = inorder_index[root_value]

            left_size = root_inorder_index - in_start
            right_size = size - 1 - left_size

            root = TreeNode(root_value)

            root.left = build(
                pre_start + 1,
                in_start,
                left_size,
            )

            root.right = build(
                pre_start + 1 + left_size,
                root_inorder_index + 1,
                right_size,
            )

            return root

        return build(0, 0, len(preorder))

Each variable has a specific obligation:

• pre_start identifies the current root in preorder.
• in_start identifies the current inorder segment.
• size guarantees both segments describe the same number of nodes.
• root_inorder_index finds the structural split.
• left_size determines both the left subtree size and the right subtree's preorder offset.
• right_size prevents the right recursion from consuming nodes outside the current subtree.

During an interview, I would perform a short code-reading pass in this order:

1. Does size == 0 return None?
2. Is the root read from preorder[pre_start]?
3. Is the inorder position found through the map?
4. Is left_size measured relative to in_start?
5. Does the right preorder start skip both the root and the left subtree?
6. Are both child results attached before returning the root?

That sequence catches the errors that examples often fail to expose.

Complexity, edge cases, and failure modes

Let n be the number of nodes.

Complexity

• Building the inorder map visits every value once: O(n).
• Each tree node is created once.
• Each map lookup takes average-case O(1).

Therefore the total time complexity is:

O(n)

The map stores n entries, and the recursion stack can contain up to n calls for a completely skewed tree:

O(n) extra space

The balanced case uses a smaller recursion depth, but the worst-case stack remains linear.

Important edge cases

• Single node: both arrays contain one value. The helper creates one node and returns two empty children.
• Empty recursive interval: any call with size == 0 must return None.
• Balanced tree: both child calls receive nonzero sizes.
• All-left tree: every right subtree has size zero.
• All-right tree: every left subtree has size zero.
• Unique values: the direct inorder map lookup is valid because each value has exactly one inorder position.

Common failure modes

Scanning inorder in every call.
This preserves the basic idea but can degrade to O(n²). If the interview asks for the linear-time solution, precompute the map.

Using the inorder index as a preorder offset.
The two arrays use different coordinate systems. The right subtree's preorder start depends on the number of nodes in the left subtree:

pre_start + 1 + left_size

It does not depend directly on root_inorder_index.

Slicing arrays at every recursion.
Slicing makes the code look compact, but it copies elements repeatedly and hides the segment boundaries. Use indices or sizes so the intended complexity remains visible.

Advancing a shared preorder pointer inconsistently.
A global pointer can work, but then its movement must follow the recursive preorder order exactly. The explicit pre_start state makes the alignment easier to inspect and debug.

Ignoring duplicate values in a different problem.
With duplicate values, a simple value-to-index map cannot identify which occurrence is the current root. This problem excludes duplicates, so the map-based solution is sufficient.

The transferable recognition rule is broader than this one tree problem:

When one representation reveals the next root or pivot, and another representation partitions the remaining elements around it, look for recursive interval decomposition.

Before coding, write the helper's segment invariant. Then derive the right-subtree offset from the left-subtree size. That small discipline turns a memorized formula into a construction you can reason about—and keeps one misplaced index from collapsing the whole tree.