Construct Binary Tree from Preorder and Inorder (LeetCode 105)

The problem

You get two lists for the same binary tree: its preorder traversal (node, left, right) and its inorder traversal (left, node, right). All values are distinct. Rebuild the tree and return its root.

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

Output:     3
           / \
          9   20
             /  \
            15   7

Level order: [3, 9, 20, null, null, 15, 7]

Preorder starts with 3, so 3 is the root. In the inorder list, 9 is left of 3 and 15, 20, 7 are right of it, so those are the two subtrees.

How to think about it

Look at what each traversal tells you. Preorder always lists a root before anything in its subtrees, so preorder[0] is the root of the whole tree. Inorder puts a root between its left and right subtrees, so finding the root’s position in inorder tells you exactly which values go left and which go right. Neither list is enough alone; together they pin the tree down.

The brute-force version follows that directly: take the root from preorder, scan inorder to find it, slice both lists into left and right parts, and recurse. It’s correct, but the scan is O(n) per node and the slices copy data, so it’s O(n²) on a skewed tree.

The key insight: avoid the scan and the slices. Build a value → inorder index map once, so finding a root is O(1). Instead of slicing, recurse on index ranges (lo, hi) of the inorder list. For preorder you don’t need ranges at all: if you build the left subtree fully before the right, the roots you need come off preorder in exactly the order it lists them. So just consume it with an iterator.

Which pattern is this? Tree DFS as divide and conquer. The tell is “build a tree from traversals”: find the root, split around it, recurse on each side.

Approach

1. Map each value to its index in inorder.
2. Make an iterator over preorder.
3. helper(lo, hi) builds the subtree whose values are inorder[lo..hi]. If lo > hi, it’s empty: return None.
4. Otherwise take the next preorder value as this subtree’s root and look up its inorder index mid.
5. Build the left child from (lo, mid - 1), then the right child from (mid + 1, hi).
6. Return helper(0, n - 1).

Solution

def build_tree_pre_in(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}              # value -> position in inorder, O(1) lookup
    nxt = iter(preorder)                                     # roots come out in preorder order
    def helper(lo, hi):
        if lo > hi: return None                              # empty range: no subtree
        val = next(nxt); node = TreeNode(val); mid = idx[val]
        node.left = helper(lo, mid - 1); node.right = helper(mid + 1, hi)   # left MUST be built first
        return node
    return helper(0, len(inorder) - 1)
# build from pre [3,9,20,15,7], in [9,3,15,20,7] -> tree[3,9,20,null,null,15,7]

Dry run

On the example. Each row is one call that creates a node:

The result, level by level, is [[3], [9, 20], [15, 7]].

Complexity

• Time: O(n). Building the map is O(n), and each value creates exactly one node with O(1) work.
• Space: O(n). The index map holds n entries; the recursion stack adds O(h).

Edge cases and pitfalls

• Empty lists return None (helper(0, -1) hits the base case).
• Order of recursion matters. Building the right subtree first would pull the wrong roots off the preorder iterator. This is the bug people hit most often.
• Duplicate values break it. The index map assumes each value appears once; LeetCode guarantees that.
• Skewed trees recurse n deep. For very large inputs, Python’s recursion limit becomes an issue.

Related problems

• Serialize and Deserialize Binary Tree (LeetCode 297): rebuilding from a preorder stream, with null markers instead of inorder.
• Validate Binary Search Tree (LeetCode 98): another recursion over a range that narrows at each node.
• Kth Smallest Element in a BST (LeetCode 230): practise the inorder traversal this problem depends on.