Problem Statement

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.

Additional information

• 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.

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]

Recursive Slicing (Intuitive but Sub-optimal)

Intuition

To reconstruct the tree, we need to understand the properties of the two traversals:

1. Preorder (Node -> Left -> Right): The very first element in the preorder array is always the root node of the current tree/subtree.
2. Inorder (Left -> Node -> Right): Once we know the root node (from the preorder array), we can find it in the inorder array. Everything to the left of this root in the inorder array belongs to the left subtree, and everything to the right belongs to the right subtree.

We can extract the root, slice the arrays into left and right components, and recursively build the subtrees.

Algorithm

1. Base Case: If preorder or inorder is empty, return None.
2. Create Root: The root's value is preorder[0]. Create a TreeNode with this value.
3. Find Midpoint: Find the index of this root value in the inorder array. Let's call it mid.
4. Recurse: * Build the left subtree using the left slices: preorder[1 : mid + 1] and inorder[:mid].

• Build the right subtree using the right slices: preorder[mid + 1:] and inorder[mid + 1:].

5. Return the constructed root.

def build_tree(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
    if not preorder or not inorder:
        return None
        
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    # Find the root's position in the inorder array
    mid = inorder.index(root_val)
    
    # Recursively build left and right subtrees
    root.left = build_tree(preorder[1:mid + 1], inorder[:mid])
    root.right = build_tree(preorder[mid + 1:], inorder[mid + 1:])
    
    return root

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: Finding the element in the inorder list using .index() takes O(n) time. Slicing the arrays also takes O(n) time. Doing this recursively for every node yields O(n^2) in the worst case (a skewed tree).

• Space complexity: O(n^2)

• Reason: Passing sliced copies of the arrays at each recursive step consumes significant memory, bounded by O(n^2) in the worst case.

Recursion with Hash Map (Optimal)

Intuition

We can optimize the two bottlenecks from the previous approach:

1. Stop Slicing: Instead of creating new arrays at every step, we can just pass left and right integer pointers (indices) that define the boundaries of the current subtree within the original inorder array.
2. Stop Searching: Instead of doing a linear scan .index() to find the root in the inorder array, we can pre-compute a Hash Map (dictionary) that stores the exact index of every value: {value: index}. This reduces lookup time to O(1).

Algorithm

1. Create a dictionary inorder_map mapping every value in inorder to its index.
2. Create a variable preorder_index starting at 0 to track which root we are currently processing in the preorder array. We will increment this as we build the tree.
3. Create a helper function build(left, right):

• If left > right, there are no elements to construct, return None.
• Get the current root value root_val = preorder[preorder_index]. Increment preorder_index.
• Create root = TreeNode(root_val).
• Find the root's index in the inorder array: mid = inorder_map[root_val].
• Recursively build the left child: root.left = build(left, mid - 1).
• Recursively build the right child: root.right = build(mid + 1, right).
• Return root.

4. Call build(0, len(inorder) - 1) and return the result.

def build_tree(preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    preorder_index = 0
    
    def build(left, right):
        nonlocal preorder_index
        if left > right:
            return None
            
        root_val = preorder[preorder_index]
        root = TreeNode(root_val)
        preorder_index += 1
        
        mid = inorder_map[root_val]
        
        # It's crucial to build the left subtree first, 
        # because the preorder traversal naturally processes left children next.
        root.left = build(left, mid - 1)
        root.right = build(mid + 1, right)
        
        return root
        
    return build(0, len(inorder) - 1)

Time & Space Complexity

• Time complexity: O(n)

• Reason: We build the hash map in O(n) time, and then we visit each node exactly once to construct it, doing O(1) work per node.

• Space complexity: O(n)

• Reason: The inorder_map requires O(n) space. The recursion stack takes O(h) space, where h is the height of the tree (up to O(n) in the worst case).