#105MediumTrees & BST

Construct Binary Tree from Preorder and Inorder Traversal

The tell: Rebuild a tree from two traversals, which together determine it uniquely.

How you get there

1Preorder's first element is always the current root.
2That value's position in inorder splits it into left and right subtrees.
3A value-to-index map makes the split O(1) instead of a scan.

Solution

Python

def build_tree(preorder: list[int], inorder: list[int]):
    index = {v: i for i, v in enumerate(inorder)}
    self_pos = 0

    def build(lo: int, hi: int):
        nonlocal self_pos
        if lo > hi:
            return None
        value = preorder[self_pos]
        self_pos += 1
        node = TreeNode(value)
        mid = index[value]
        node.left = build(lo, mid - 1)      # must build left first
        node.right = build(mid + 1, hi)
        return node

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

Time: O(n)
Space: O(n)

What goes wrong

Building the right subtree before the left consumes preorder in the wrong order.

Test yourself on DSA Next: Balanced Binary Tree →