Construct Binary Tree from Preorder and Inorder Traversal

Difficulty: Medium Source: NeetCode

Problem

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]

Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1]

Constraints:

1 <= preorder.length <= 3000

inorder.length == preorder.length

-3000 <= preorder[i], inorder[i] <= 3000

preorder and inorder consist of unique values

Each value of inorder also appears in preorder

preorder is guaranteed to be the preorder traversal of the tree

inorder is guaranteed to be the inorder traversal of the tree

Prerequisites

Before attempting this problem, you should be comfortable with:

Preorder Traversal — Root is always the first element
Inorder Traversal — Left subtree values come before root, right subtree values come after
Divide and Conquer — Using the root to split the problem into left and right subproblems
Hash Map — O(1) lookup for the root’s position in inorder array

1. Recursive with Hash Map (Optimal)

The first element of preorder is always the root. Once we know the root, we find it in inorder — everything to its left belongs to the left subtree, everything to its right belongs to the right subtree. We can recursively apply this to build the whole tree. We use a hash map for O(1) lookups in the inorder array.

Algorithm

Build a {value: index} map for the inorder array
Use a pointer into preorder (or index) to track the next root
build(in_left, in_right) function:
- The next preorder value is the root
- Find root’s index in inorder using the hash map
- left_size = root_idx - in_left
- Recursively build left subtree: build(in_left, root_idx - 1)
- Recursively build right subtree: build(root_idx + 1, in_right)
Return root node

Solution

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

def build_tree(preorder, inorder):
    # Map each value to its index in inorder for O(1) lookup
    inorder_idx = {val: i for i, val in enumerate(inorder)}
    pre_ptr = [0]  # Use list so we can mutate inside nested function

    def build(in_left, in_right):
        if in_left > in_right:
            return None

        # Next root is the current preorder element
        root_val = preorder[pre_ptr[0]]
        pre_ptr[0] += 1
        root = TreeNode(root_val)

        # Find root in inorder to split left/right
        mid = inorder_idx[root_val]

        # Build left subtree first (preorder visits left before right)
        root.left = build(in_left, mid - 1)
        root.right = build(mid + 1, in_right)

        return root

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

# --- helpers ---
def level_order(root):
    if not root:
        return []
    result, queue = [], [root]
    while queue:
        node = queue.pop(0)
        result.append(node.val if node else None)
        if node:
            queue.append(node.left)
            queue.append(node.right)
    # Trim trailing Nones
    while result and result[-1] is None:
        result.pop()
    return result

def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

def preorder_traversal(root):
    if not root:
        return []
    return [root.val] + preorder_traversal(root.left) + preorder_traversal(root.right)

# --- tests ---
pre1 = [3, 9, 20, 15, 7]
ino1 = [9, 3, 15, 20, 7]
root1 = build_tree(pre1, ino1)
print("Level order:", level_order(root1))   # [3, 9, 20, 15, 7]
print("Preorder:", preorder_traversal(root1))  # [3, 9, 20, 15, 7]
print("Inorder:", inorder_traversal(root1))    # [9, 3, 15, 20, 7]

pre2 = [-1]
ino2 = [-1]
root2 = build_tree(pre2, ino2)
print("Single node:", root2.val)  # -1

# More complex
pre3 = [1, 2, 4, 5, 3, 6, 7]
ino3 = [4, 2, 5, 1, 6, 3, 7]
root3 = build_tree(pre3, ino3)
print("Preorder check:", preorder_traversal(root3))  # [1, 2, 4, 5, 3, 6, 7]
print("Inorder check:", inorder_traversal(root3))    # [4, 2, 5, 1, 6, 3, 7]

Complexity

Time: O(n) — each node created once; hash map gives O(1) lookup
Space: O(n) — hash map + recursion stack

2. Naive (Without Hash Map)

Intuition

Same approach but we do a linear search in inorder each time instead of using a hash map. Simpler to write but much slower.

Solution

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

def build_tree_naive(preorder, inorder):
    if not preorder or not inorder:
        return None

    root_val = preorder[0]
    root = TreeNode(root_val)

    mid = inorder.index(root_val)  # O(n) linear search

    root.left = build_tree_naive(preorder[1:mid + 1], inorder[:mid])
    root.right = build_tree_naive(preorder[mid + 1:], inorder[mid + 1:])

    return root

# --- test ---
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_tree_naive(pre, ino)

def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

print(inorder_traversal(root))  # [9, 3, 15, 20, 7]

Complexity

Time: O(n²) — linear search in inorder at each recursion level
Space: O(n²) — list slicing creates new arrays at each level

Common Pitfalls

Building the right subtree before the left. Preorder visits left before right, so you must consume preorder elements for the left subtree first. If you build right first, you’ll assign wrong values to nodes.

Slicing arrays at each recursion level. Array slicing creates new lists — O(n) per call leading to O(n²) total. Use index bounds instead and a hash map for the inorder lookup to get O(n).

Keyboard shortcuts

Note Book