Problem Description

You are given two integer arrays representing different traversals of the same binary tree:

• preorder: the preorder traversal (root → left → right)
• inorder: the inorder traversal (left → root → right)

Your task is to reconstruct and return the original binary tree from these two traversals.

The problem leverages the properties of tree traversals:

• In preorder traversal, the first element is always the root node
• In inorder traversal, elements to the left of the root are in the left subtree, and elements to the right are in the right subtree

The solution uses a recursive approach with a hash table for efficient lookups. The key insight is that once we identify the root from preorder[0], we can find its position in the inorder array to determine which elements belong to the left and right subtrees.

The recursive function dfs(i, j, n) builds the tree where:

• i is the starting index in the preorder array
• j is the starting index in the inorder array
• n is the number of nodes to process

For each recursive call:

1. The root value is taken from preorder[i]
2. Its position k in the inorder array is found using the hash table
3. The left subtree has k - j nodes (elements before root in inorder)
4. The right subtree has n - k + j - 1 nodes (elements after root in inorder)
5. Recursively build left and right subtrees with appropriate index ranges
6. Return a TreeNode with the root value and constructed subtrees

The hash table d maps each value to its index in the inorder array for O(1) lookups, making the overall time complexity O(n).

Intuition

The key observation is understanding what preorder and inorder traversals tell us about the tree structure.

In preorder traversal, we visit nodes in the order: root → left subtree → right subtree. This means the first element is always the root of the current tree or subtree.

In inorder traversal, we visit nodes in the order: left subtree → root → right subtree. This means all nodes to the left of the root value belong to the left subtree, and all nodes to the right belong to the right subtree.

By combining these two properties, we can reconstruct the tree recursively:

1. Pick the first element from preorder - this is our root
2. Find this root in inorder - this splits our nodes into left and right groups
3. Count how many nodes are in the left subtree (elements before root in inorder)
4. Use this count to determine which elements in preorder belong to left vs right subtrees

For example, if preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7]:

• Root is 3 (first in preorder)
• In inorder, 9 is left of 3, so it's in left subtree
• 15,20,7 are right of 3, so they're in right subtree
• In preorder, after root 3, the next 1 element (9) forms the left subtree
• The remaining elements (20,15,7) form the right subtree

The challenge is efficiently tracking which portions of the arrays correspond to which subtree. We use index arithmetic: if we know the starting positions and the number of nodes, we can calculate the exact array segments for each recursive call.

The hash table optimization comes from needing to repeatedly find where the root appears in inorder. Instead of searching each time (O(n)), we precompute all positions (O(1) lookup).

Solution Approach

The solution uses a hash table combined with recursion to efficiently reconstruct the binary tree.

Step 1: Build Hash Table

d = {v: i for i, v in enumerate(inorder)}

We create a dictionary d that maps each node value to its index in the inorder array. This allows O(1) lookup time when finding the root's position.

Step 2: Define Recursive Function The core function dfs(i, j, n) takes three parameters:

• i: starting index in the preorder array
• j: starting index in the inorder array
• n: number of nodes to process in this subtree

Step 3: Base Case

if n <= 0:
    return None

If there are no nodes to process, return None.

Step 4: Identify Root and Split Point

v = preorder[i]  # Root value
k = d[v]         # Root's position in inorder

The root is always at preorder[i]. We find its position k in the inorder array using our hash table.

Step 5: Calculate Subtree Sizes

• Left subtree size: k - j (nodes before root in inorder segment)
• Right subtree size: n - k + j - 1 (nodes after root in inorder segment)

Step 6: Recursive Construction

l = dfs(i + 1, j, k - j)                    # Left subtree
r = dfs(i + 1 + k - j, k + 1, n - k + j - 1)  # Right subtree

For the left subtree:

• Preorder starts at i + 1 (skip the root)
• Inorder starts at j (same start)
• Process k - j nodes

For the right subtree:

• Preorder starts at i + 1 + k - j (skip root and all left subtree nodes)
• Inorder starts at k + 1 (skip left subtree and root)
• Process n - k + j - 1 nodes

Step 7: Build and Return Node

return TreeNode(v, l, r)

Create a new TreeNode with value v, left child l, and right child r.

The initial call dfs(0, 0, len(preorder)) starts with the entire arrays and recursively builds the complete tree from top to bottom.

Example Walkthrough

Let's trace through a small example with preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7].

Initial Setup:

• Build hash table: d = {9:0, 3:1, 15:2, 20:3, 7:4}
• Call dfs(0, 0, 5) to process all 5 nodes

First Call: dfs(0, 0, 5)

• Root value: preorder[0] = 3
• Find root position: d[3] = 1
• Left subtree size: 1 - 0 = 1 node
• Right subtree size: 5 - 1 + 0 - 1 = 3 nodes
• Build left: dfs(1, 0, 1)
• Build right: dfs(2, 2, 3)

Left Subtree: dfs(1, 0, 1)

• Root value: preorder[1] = 9
• Find root position: d[9] = 0
• Left subtree size: 0 - 0 = 0 nodes → returns None
• Right subtree size: 1 - 0 + 0 - 1 = 0 nodes → returns None
• Returns: TreeNode(9)

Right Subtree: dfs(2, 2, 3)

• Root value: preorder[2] = 20
• Find root position: d[20] = 3
• Left subtree size: 3 - 2 = 1 node
• Right subtree size: 3 - 3 + 2 - 1 = 1 node
• Build left: dfs(3, 2, 1) → returns TreeNode(15)
• Build right: dfs(4, 4, 1) → returns TreeNode(7)
• Returns: TreeNode(20, TreeNode(15), TreeNode(7))

Final Tree Structure:

      3
     / \
    9   20
       /  \
      15   7

The algorithm correctly reconstructs the tree by using preorder to identify roots and inorder to determine subtree boundaries. Each recursive call processes a specific segment of both arrays, building the tree from top to bottom.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm builds a binary tree from preorder and inorder traversals. The main operations are:

• Creating a hash map d from the inorder list takes O(n) time
• The recursive function dfs visits each node exactly once to construct the tree
• At each node, we perform constant time operations: finding the value in the hash map (O(1)), creating a TreeNode (O(1)), and making recursive calls
• Since we process each of the n nodes exactly once with O(1) work per node, the total time complexity is O(n)

Space Complexity: O(n)

The space usage comes from:

• The hash map d storing the inorder indices requires O(n) space
• The recursion stack depth in the worst case (skewed tree) can be O(n)
• The output tree itself contains n nodes, requiring O(n) space
• Therefore, the overall space complexity is O(n)

Common Pitfalls

1. Index Calculation Errors for Right Subtree

One of the most common mistakes is incorrectly calculating the starting index or size for the right subtree, especially the preorder starting index.

Incorrect Implementation:

# Wrong: forgetting to account for left subtree size
right_child = build_subtree(
    preorder_start + 1,  # ❌ This would re-process left subtree nodes
    root_inorder_index + 1,
    subtree_size - left_subtree_size - 1
)

Correct Implementation:

# Correct: skip root AND all left subtree nodes
right_child = build_subtree(
    preorder_start + 1 + left_subtree_size,  # ✓ Skip root + left subtree
    root_inorder_index + 1,
    subtree_size - left_subtree_size - 1
)

2. Assuming No Duplicate Values

The solution relies on a hash map to find the root's position in the inorder array. If duplicate values exist, the hash map will only store the last occurrence's index, leading to incorrect tree construction.

Problem Example:

preorder = [1, 2, 1, 3]
inorder = [1, 2, 1, 3]
# Hash map would be {1: 2, 2: 1, 3: 3}, losing the first '1' at index 0

Solution: Instead of using a global hash map, pass the valid range and search within that range:

def build_subtree(pre_start, in_start, in_end):
    if pre_start >= len(preorder) or in_start > in_end:
        return None
  
    root_val = preorder[pre_start]
    # Search only within the valid inorder range
    root_index = -1
    for i in range(in_start, in_end + 1):
        if inorder[i] == root_val:
            root_index = i
            break
  
    # Continue with tree construction...

3. Off-by-One Errors in Size Calculations

Calculating the right subtree size incorrectly is another frequent mistake.

Incorrect:

# Wrong: forgetting to subtract 1 for the root
right_subtree_size = subtree_size - left_subtree_size  # ❌

Correct:

# Correct: total size - left subtree - root (1)
right_subtree_size = subtree_size - left_subtree_size - 1  # ✓

4. Not Handling Edge Cases

Failing to handle empty arrays or single-node trees can cause runtime errors.

Add validation:

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    # Handle edge cases
    if not preorder or not inorder:
        return None
    if len(preorder) != len(inorder):
        raise ValueError("Traversal arrays must have the same length")
  
    # Continue with normal logic...

5. Mixing Up Array Boundaries

Using absolute indices instead of relative positions within the current subtree segment.

Incorrect Approach (using global indices):

def dfs(pre_left, pre_right, in_left, in_right):
    if pre_left > pre_right:
        return None
    # Complex index management...

Better Approach (using start + size):

def dfs(pre_start, in_start, size):
    if size <= 0:
        return None
    # Cleaner, less error-prone

The start + size approach used in the solution is generally cleaner and reduces the chance of boundary errors compared to maintaining four separate boundary indices.