Problem 32 · Trees

Construct Binary Tree from Preorder and Inorder Traversal

MediumClassic DSA & systems

01Problem

Given preorder and inorder traversals of a binary tree with unique values, reconstruct and return the tree.

02Key insight

Preorder gives the next root; inorder tells you when a left spine ends. Keep a stack of the current left path: each new preorder value is the left child of the stack top until the top matches inorder[j]; then pop matched ancestors and attach the value as a right child. O(n) with no recursion, so skewed trees don't overflow.

03Solution

solution.pypython27 lines

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None

def build_tree(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
    if not preorder:
        return None
    root = TreeNode(preorder[0])
    stack, j = [root], 0
    for val in preorder[1:]:
        node = stack[-1]
        if node.val != inorder[j]:  # still descending the left spine
            node.left = TreeNode(val)
            stack.append(node.left)
            continue
        while stack and stack[-1].val == inorder[j]:  # left subtree done: climb
            node = stack.pop()
            j += 1
        node.right = TreeNode(val)
        stack.append(node.right)
    return root

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 8 passing

tests.pypython16 lines

T = TreeNode
assert build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]) == T(3, T(9), T(20, T(15), T(7)))
assert build_tree([], []) is None
assert build_tree([1, 2, 3], [3, 2, 1]) == T(1, T(2, T(3)))
assert build_tree([1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 6, 3]) == T(1, T(2, T(4), T(5)), T(3, T(6)))
n = 1500  # skewed trees: no RecursionError
node, depth = build_tree(list(range(n)), list(range(n - 1, -1, -1))), 0
while node:
    assert node.val == depth and node.right is None
    node, depth = node.left, depth + 1
assert depth == n
node, depth = build_tree(list(range(n)), list(range(n))), 0
while node:
    assert node.val == depth and node.left is None
    node, depth = node.right, depth + 1
assert depth == n

04Staff-level follow-up

Values may repeat? Then the traversals are ambiguous; you need node ids or null markers (as in serialization) to reconstruct uniquely.