105. Construct Binary Tree from Preorder and Inorder Traversal (Medium)

Problem

Given two integer arrays preorder and inorder representing the preorder and inorder traversals of a binary tree (assume unique values), reconstruct and return the tree.

Example

• preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] → [3,9,20,null,null,15,7]
• preorder = [-1], inorder = [-1] → [-1]

LeetCode 105 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Approach 1: Recursive with list.index per call

First element of preorder is the root. Find it in inorder to split left/right subtrees. Recurse.

Python

def build_tree(preorder, inorder):
    if not preorder:
        return None
    root_val = preorder[0]                         # L1: O(1)
    root = TreeNode(root_val)
    mid = inorder.index(root_val)                  # L2: O(n) linear scan
    root.left = build_tree(preorder[1:mid + 1], inorder[:mid])        # L3: O(n) slice
    root.right = build_tree(preorder[mid + 1:], inorder[mid + 1:])   # L4: O(n) slice
    return root

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    if (!preorder.length) return null;
    const rootVal = preorder[0];                           // L1: O(1)
    const root = new TreeNode(rootVal);
    const mid = inorder.indexOf(rootVal);                  // L2: O(n) linear scan
    root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid));      // L3: O(n) slice
    root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1));       // L4: O(n) slice
    return root;
}

Swift

final class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? { guard let rootValue = preorder.first, let middle = inorder.firstIndex(of: rootValue) else { return nil }; let root = TreeNode(rootValue); root.left = buildTree(Array(preorder[1..<(middle + 1)]), Array(inorder[..<middle])); root.right = buildTree(Array(preorder[(middle + 1)...]), Array(inorder[(middle + 1)...])); return root }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (read first)	$O(1)$	n	$O(n)$
L2 (list.index)	$O(n)$	n	$O(n²)$ ← dominates
L3/L4 (slicing)	$O(n)$	n	$O(n²)$

Both L2 and L3/L4 are $O(n)$ per call, and both are called $O(n)$ times total. The n² comes from re-scanning the inorder array at every level of recursion.

Complexity

• Time: $O(n²)$. list.index is $O(n)$; called $O(n)$ times.
• Space: $O(n²)$ across slices; $O(n)$ for the tree.

Approach 2: Hash map inorder index + pointer recursion (optimal)

Precompute val → index in inorder once ($O(n)$). Pass index ranges into the recursion instead of slicing.

Python

def build_tree(preorder, inorder):
    inorder_idx = {v: i for i, v in enumerate(inorder)}  # L1: O(n) build map
    pre_i = [0]

    def rec(in_l, in_r):
        if in_l > in_r:
            return None
        root_val = preorder[pre_i[0]]           # L2: O(1) index into preorder
        pre_i[0] += 1                           # L3: O(1) advance pointer
        root = TreeNode(root_val)
        mid = inorder_idx[root_val]             # L4: O(1) hash lookup
        root.left = rec(in_l, mid - 1)          # L5: recurse left subtree
        root.right = rec(mid + 1, in_r)         # L6: recurse right subtree
        return root

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

TypeScript

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    const inorderIdx = new Map<number, number>();
    inorder.forEach((v, i) => inorderIdx.set(v, i));  // L1: O(n) build map
    let preI = 0;

    function rec(inL: number, inR: number): TreeNode | null {
        if (inL > inR) return null;
        const rootVal = preorder[preI++];              // L2/L3: O(1) read + advance
        const root = new TreeNode(rootVal);
        const mid = inorderIdx.get(rootVal)!;          // L4: O(1) hash lookup
        root.left = rec(inL, mid - 1);                 // L5: recurse left subtree
        root.right = rec(mid + 1, inR);                // L6: recurse right subtree
        return root;
    }

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

Swift

final class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? { let positions = Dictionary(uniqueKeysWithValues: inorder.enumerated().map { ($0.element, $0.offset) }); var preorderIndex = 0; func build(_ left: Int, _ right: Int) -> TreeNode? { guard left <= right else { return nil }; let value = preorder[preorderIndex]; preorderIndex += 1; guard let middle = positions[value] else { return nil }; let node = TreeNode(value); node.left = build(left, middle - 1); node.right = build(middle + 1, right); return node }; return build(0, inorder.count - 1) }
}

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height.

Line	Per-call cost	Times executed	Contribution
L1 (build map)	$O(n)$	1	$O(n)$
L2 (read preorder)	$O(1)$	n	$O(n)$
L3 (advance pointer)	$O(1)$	n	$O(n)$
L4 (hash lookup)	$O(1)$	n	$O(n)$ ← dominates (all per-node lines tie)
L5/L6 (recurse)	$O(1)$ dispatch	n	$O(n)$

Every node is constructed in $O(1)$ given the precomputed map. No slicing, no scanning.

Complexity

• Time: $O(n)$. Each node constructed in $O(1)$ given the index.
• Space: $O(n)$ for the map + $O(h)$ recursion.

Why the preorder index is shared state

We consume the preorder from left to right, but we must process the left subtree completely before starting the right subtree. By sharing a single counter (pre_i) across recursive calls, the left subtree’s exhaustion naturally positions us at the right subtree’s root.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Iterative with a stack

More code; rarely preferred unless recursion depth is a specific concern. The iterative form pushes preorder values while walking the inorder until the top matches; then pops and assigns to the next preorder root.

Python

def build_tree(preorder, inorder):
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    stack = [root]
    in_idx = 0
    for i in range(1, len(preorder)):
        node = TreeNode(preorder[i])
        if stack[-1].val != inorder[in_idx]:
            # Top hasn't been "completed" by inorder yet → current is its left child
            stack[-1].left = node
        else:
            # Pop while top matches inorder cursor (we've walked past their subtrees)
            popped = None
            while stack and stack[-1].val == inorder[in_idx]:
                popped = stack.pop()
                in_idx += 1
            # The last popped node is the parent whose right subtree starts here
            popped.right = node
        stack.append(node)
    return root

Swift

final class Solution {
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? { guard let first = preorder.first else { return nil }; let root = TreeNode(first); var stack = [root], inorderIndex = 0; for value in preorder.dropFirst() { var node = stack[stack.count - 1]; if node.val != inorder[inorderIndex] { node.left = TreeNode(value); if let left = node.left { stack.append(left) } } else { while let last = stack.last, last.val == inorder[inorderIndex] { node = stack.removeLast(); inorderIndex += 1 }; node.right = TreeNode(value); if let right = node.right { stack.append(right) } } }; return root }
}

The invariant: the stack holds the current path of “left-child ancestors.” When the top matches the inorder cursor, we’ve finished a left subtree, and the next preorder value belongs to a right child further up the path. The pop-while loop walks up to find which one.

Complexity

• Time: $O(n)$. Each node is pushed and popped once.
• Space: $O(n)$ for the stack.

Summary

Approach	Time	Space
Recursive with list.index	$O(n²)$	$O(n²)$ slices
Hash map + recursion	$O(n)$	$O(n)$
Iterative stack	$O(n)$	$O(n)$

The hash-map + recursion pattern generalizes to problem 106 (Build from Inorder + Postorder), same code with the preorder cursor replaced by a right-to-left postorder cursor.

Test cases

Python

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):
    inorder_idx = {v: i for i, v in enumerate(inorder)}
    pre_i = [0]

    def rec(in_l, in_r):
        if in_l > in_r:
            return None
        root_val = preorder[pre_i[0]]
        pre_i[0] += 1
        root = TreeNode(root_val)
        mid = inorder_idx[root_val]
        root.left = rec(in_l, mid - 1)
        root.right = rec(mid + 1, in_r)
        return root

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

def tree_to_list(root):
    """Level-order serialize for comparison."""
    if not root:
        return []
    from collections import deque
    result, q = [], deque([root])
    while q:
        node = q.popleft()
        if node:
            result.append(node.val)
            q.append(node.left)
            q.append(node.right)
        else:
            result.append(None)
    # strip trailing Nones
    while result and result[-1] is None:
        result.pop()
    return result

def _run_tests():
    # example from problem
    t = build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])
    assert tree_to_list(t) == [3, 9, 20, None, None, 15, 7]
    # single node
    t2 = build_tree([-1], [-1])
    assert t2.val == -1
    assert t2.left is None and t2.right is None
    # left-skewed
    t3 = build_tree([1, 2, 3], [3, 2, 1])
    assert tree_to_list(t3) == [1, 2, None, 3]
    # right-skewed
    t4 = build_tree([1, 2, 3], [1, 2, 3])
    assert tree_to_list(t4) == [1, None, 2, None, 3]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    const inorderIdx = new Map<number, number>();
    inorder.forEach((v, i) => inorderIdx.set(v, i));
    let preI = 0;
    function rec(inL: number, inR: number): TreeNode | null {
        if (inL > inR) return null;
        const rootVal = preorder[preI++];
        const root = new TreeNode(rootVal);
        const mid = inorderIdx.get(rootVal)!;
        root.left = rec(inL, mid - 1);
        root.right = rec(mid + 1, inR);
        return root;
    }
    return rec(0, inorder.length - 1);
}

function treeToList(root: TreeNode | null): (number | null)[] {
    if (!root) return [];
    const result: (number | null)[] = [];
    const q: (TreeNode | null)[] = [root];
    while (q.length) {
        const node = q.shift()!;
        if (node) { result.push(node.val); q.push(node.left); q.push(node.right); }
        else result.push(null);
    }
    while (result.length && result[result.length - 1] === null) result.pop();
    return result;
}

const t = buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]);
console.assert(JSON.stringify(treeToList(t)) === JSON.stringify([3, 9, 20, null, null, 15, 7]));
const t2 = buildTree([-1], [-1]);
console.assert(t2!.val === -1 && t2!.left === null && t2!.right === null);
const t3 = buildTree([1, 2, 3], [3, 2, 1]);
console.assert(JSON.stringify(treeToList(t3)) === JSON.stringify([1, 2, null, 3]));
const t4 = buildTree([1, 2, 3], [1, 2, 3]);
console.assert(JSON.stringify(treeToList(t4)) === JSON.stringify([1, null, 2, null, 3]));
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, reconstruction from traversals
• Hash Tables, $O(1)$ index lookup in inorder

Related concepts

• Divide and Conquer, the split, solve, and combine pattern for independent subproblems.
• Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.