Construct Binary Tree from Preorder and Inorder Traversal

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.

Solution

Approach: Recursive Divide and Conquer

The key insight is that preorder gives us the root (first element), and inorder tells us which nodes are in left vs right subtrees.

Implementation

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # Create hash map for O(1) lookup of inorder indices
        inorder_map = {val: idx for idx, val in enumerate(inorder)}
        self.preorder_idx = 0

        def build(left, right):
            if left > right:
                return None

            # Root is next element in preorder
            root_val = preorder[self.preorder_idx]
            root = TreeNode(root_val)
            self.preorder_idx += 1

            # Find root position in inorder
            inorder_idx = inorder_map[root_val]

            # Build left and right subtrees
            # Important: build left first since preorder processes left before right
            root.left = build(left, inorder_idx - 1)
            root.right = build(inorder_idx + 1, right)

            return root

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

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We visit each node once and do O(1) lookup with the hash map.
Space Complexity: O(n) for the hash map and O(h) for recursion stack, where h is the height.

Key Insights

Preorder Structure: Preorder visits root, then left subtree, then right subtree. First element is always the root.
Inorder Structure: Inorder visits left subtree, then root, then right subtree. Root position divides left and right subtrees.
Divide and Conquer: Find root from preorder, locate it in inorder to split left/right, recursively build subtrees.
Hash Map Optimization: Storing inorder indices in a hash map allows O(1) lookup instead of O(n) linear search.
Order Matters: We must build left subtree before right because preorder processes left first, and we consume preorder sequentially.