LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal

Problem Restatement

We are given two integer arrays:

preorder
inorder

Both arrays describe the same binary tree.

preorder is the preorder traversal of the tree.

inorder is the inorder traversal of the same tree.

We need to construct and return the original binary tree. The official problem states that preorder and inorder are traversals of the same tree.

The key traversal rules are:

preorder: root -> left -> right
inorder:  left -> root -> right

The node values are unique, so each value appears in exactly one place in the tree.

Input and Output

Item	Meaning
Input	Two integer arrays, `preorder` and `inorder`
Output	The root of the constructed binary tree
Preorder meaning	Root first, then left subtree, then right subtree
Inorder meaning	Left subtree, then root, then right subtree
Important condition	Node values are unique

LeetCode gives the TreeNode class:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The function shape is:

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        ...

Examples

Consider:

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

The first value in preorder is always the root:

Now find 3 in inorder:

[9] 3 [15, 20, 7]

Everything left of 3 belongs to the left subtree:

[9]

Everything right of 3 belongs to the right subtree:

[15, 20, 7]

So the tree starts like this:

        3
      /   \
     9     ?

Now build the right subtree from:

preorder right part = [20, 15, 7]
inorder right part  = [15, 20, 7]

The root is 20.

In inorder:

[15] 20 [7]

So 15 is the left child and 7 is the right child.

The final tree is:

First Thought: Use the Traversal Definitions

The traversal arrays are not arbitrary lists.

They encode structure.

Preorder tells us the root immediately:

preorder[0] is the root

Inorder tells us how to split the tree:

values before root  -> left subtree
values after root   -> right subtree

So after finding the root, we can recursively build the left and right subtrees.

Key Insight

The root of each subtree appears first in that subtree’s preorder range.

Once we know the root value, we find its position in inorder.

That position tells us the number of nodes in the left subtree.

For a subtree whose inorder range is:

in_left ... in_right

and whose root appears at:

root_index

the left subtree size is:

left_size = root_index - in_left

This size lets us split the preorder range correctly.

To avoid searching inside inorder every time, we build a hash map:

value -> index in inorder

Then each root position lookup is O(1).

Algorithm

Build a dictionary called in_pos:

in_pos[value] = index

Then define a recursive function:

build(pre_left, pre_right, in_left, in_right)

This function builds the tree from:

preorder[pre_left : pre_right + 1]
inorder[in_left : in_right + 1]

For each call:

If the preorder range is empty, return None.
The root value is preorder[pre_left].
Create a TreeNode with that value.
Find the root position in inorder using in_pos.
Compute the left subtree size.
Recursively build the left subtree.
Recursively build the right subtree.
Return the root node.

The left subtree ranges are:

preorder: pre_left + 1 to pre_left + left_size
inorder:  in_left to root_index - 1

The right subtree ranges are:

preorder: pre_left + left_size + 1 to pre_right
inorder:  root_index + 1 to in_right

Correctness

The first element of a preorder traversal is the root of the current tree. Therefore, each recursive call chooses the correct root for its current subtree.

In inorder traversal, every value before the root belongs to the left subtree, and every value after the root belongs to the right subtree. Because all values are unique, the root has one exact position in the inorder array. This gives one exact split into left and right subtrees.

The algorithm computes the size of the left subtree from that inorder split. It then uses that size to take exactly the correct number of nodes from preorder for the left subtree. The remaining nodes in the current preorder range belong to the right subtree.

The recursive calls apply the same reasoning to each subtree. When a subtree range becomes empty, the algorithm returns None, which correctly represents a missing child.

Therefore, every node is created once, attached to the correct parent, and placed in the correct left or right subtree. The returned root is the original binary tree described by the traversals.

Complexity

Metric	Value	Why
Time	`O(n)`	Each node is created once, and each inorder index lookup is constant time
Space	`O(n)`	The hash map stores `n` values, and recursion uses stack space

Here, n is the number of nodes.

The recursion stack is O(h), where h is the tree height. In the worst case, h = n.

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        in_pos = {}

        for i, value in enumerate(inorder):
            in_pos[value] = i

        def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> Optional[TreeNode]:
            if pre_left > pre_right:
                return None

            root_value = preorder[pre_left]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

            root.left = build(
                pre_left + 1,
                pre_left + left_size,
                in_left,
                root_index - 1,
            )

            root.right = build(
                pre_left + left_size + 1,
                pre_right,
                root_index + 1,
                in_right,
            )

            return root

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

Code Explanation

First, we store each value’s index in inorder:

in_pos = {}

for i, value in enumerate(inorder):
    in_pos[value] = i

This avoids repeated linear scans.

The helper function receives index boundaries:

def build(pre_left, pre_right, in_left, in_right):

These boundaries describe the current subtree.

If the preorder range is empty, there is no node to build:

if pre_left > pre_right:
    return None

The first value in the current preorder range is the root:

root_value = preorder[pre_left]
root = TreeNode(root_value)

Find where this root appears in inorder:

root_index = in_pos[root_value]

Then compute how many nodes belong to the left subtree:

left_size = root_index - in_left

Now build the left subtree:

root.left = build(
    pre_left + 1,
    pre_left + left_size,
    in_left,
    root_index - 1,
)

The left subtree starts right after the root in preorder and has left_size nodes.

Then build the right subtree:

root.right = build(
    pre_left + left_size + 1,
    pre_right,
    root_index + 1,
    in_right,
)

Finally, return the root:

return root

Testing

To test tree construction, it is easier to serialize the result back into preorder and inorder and compare them with the input.

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        in_pos = {}

        for i, value in enumerate(inorder):
            in_pos[value] = i

        def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> Optional[TreeNode]:
            if pre_left > pre_right:
                return None

            root_value = preorder[pre_left]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

            root.left = build(
                pre_left + 1,
                pre_left + left_size,
                in_left,
                root_index - 1,
            )

            root.right = build(
                pre_left + left_size + 1,
                pre_right,
                root_index + 1,
                in_right,
            )

            return root

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

def preorder_values(root):
    if root is None:
        return []

    return [root.val] + preorder_values(root.left) + preorder_values(root.right)

def inorder_values(root):
    if root is None:
        return []

    return inorder_values(root.left) + [root.val] + inorder_values(root.right)

def run_tests():
    s = Solution()

    preorder1 = [3, 9, 20, 15, 7]
    inorder1 = [9, 3, 15, 20, 7]
    root1 = s.buildTree(preorder1, inorder1)
    assert preorder_values(root1) == preorder1
    assert inorder_values(root1) == inorder1

    preorder2 = [-1]
    inorder2 = [-1]
    root2 = s.buildTree(preorder2, inorder2)
    assert preorder_values(root2) == preorder2
    assert inorder_values(root2) == inorder2

    preorder3 = [1, 2, 3, 4]
    inorder3 = [4, 3, 2, 1]
    root3 = s.buildTree(preorder3, inorder3)
    assert preorder_values(root3) == preorder3
    assert inorder_values(root3) == inorder3

    preorder4 = [1, 2, 3, 4]
    inorder4 = [1, 2, 3, 4]
    root4 = s.buildTree(preorder4, inorder4)
    assert preorder_values(root4) == preorder4
    assert inorder_values(root4) == inorder4

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[3,9,20,15,7]`, `[9,3,15,20,7]`	Standard mixed tree
Single node	Minimum valid tree
Left-skewed tree	Confirms recursive left ranges
Right-skewed tree	Confirms recursive right ranges