Problem Description

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

• inorder: the inorder traversal of a binary tree (left → root → right)
• postorder: the postorder traversal of the same tree (left → right → root)

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

The key insight is that:

• In postorder traversal, the last element is always the root of the tree
• In inorder traversal, elements to the left of the root form the left subtree, and elements to the right form the right subtree

The solution uses a recursive approach with a hash table to efficiently locate elements. The function dfs(i, j, n) reconstructs a subtree where:

• i is the starting index in the inorder array
• j is the starting index in the postorder array
• n is the number of nodes in the current subtree

The algorithm works by:

1. Finding the root from the last element of the current postorder segment (postorder[j + n - 1])
2. Locating this root's position k in the inorder array using the hash table d
3. Calculating the size of left subtree as k - i (elements before root in inorder)
4. Recursively building the left subtree with dfs(i, j, k - i)
5. Recursively building the right subtree with dfs(k + 1, j + k - i, n - k + i - 1)
6. Creating a new TreeNode with the root value and attaching the left and right subtrees

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

Intuition

The key to solving this problem lies in understanding the properties of different tree traversals:

In postorder traversal, we visit nodes in the order: left subtree → right subtree → root. This means the last element in any postorder sequence is always the root of that tree or subtree.

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

These two properties give us a way to recursively reconstruct the tree:

1. Find the root: Look at the last element in the postorder array - that's our root.

2. Partition the trees: Find where this root appears in the inorder array. Everything before it forms the left subtree, everything after forms the right subtree.

3. Determine subtree boundaries: If the root is at position k in inorder, and we start from position i, then we have k - i nodes in the left subtree. This tells us how to split both arrays for recursive calls.

4. Recursive construction: For the left subtree, we take the first k - i elements from both arrays (adjusted for their starting positions). For the right subtree, we take the remaining elements except the root.

The challenge is tracking the correct indices as we recurse. Since we're working with subarrays conceptually, we need to maintain:

• Starting positions in both arrays (i for inorder, j for postorder)
• The number of nodes in the current subtree (n)

Using a hash table to store inorder positions eliminates the need to search for the root position each time, reducing our lookup from O(n) to O(1) and making the overall algorithm more efficient.

Solution Approach

The solution uses a hash table + recursion approach to efficiently reconstruct the binary tree.

Step 1: Build the Hash Table

First, we create a hash table d that maps each value in the inorder array to its index:

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

This allows O(1) lookup of any node's position in the inorder traversal.

Step 2: Define the Recursive Function

We define dfs(i, j, n) where:

• i = starting index in the inorder array
• j = starting index in the postorder array
• n = number of nodes in the current subtree

Step 3: Base Case

If n <= 0, the subtree is empty, so we return None.

Step 4: Find the Root

The root of the current subtree is always the last element in its postorder segment:

v = postorder[j + n - 1]

Step 5: Locate Root in Inorder

Use the hash table to find the root's position in the inorder array:

k = d[v]

Step 6: Calculate Subtree Sizes

• Left subtree size: k - i (nodes before the root in inorder)
• Right subtree size: n - k + i - 1 (total nodes minus root minus left subtree)

Step 7: Recursively Build Subtrees

Build the left subtree:

l = dfs(i, j, k - i)

• Inorder: starts at i, contains k - i nodes
• Postorder: starts at j, contains k - i nodes

Build the right subtree:

r = dfs(k + 1, j + k - i, n - k + i - 1)

• Inorder: starts at k + 1 (after root)
• Postorder: starts at j + k - i (after left subtree nodes)
• Contains n - k + i - 1 nodes

Step 8: Construct and Return Node

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

return TreeNode(v, l, r)

The initial call dfs(0, 0, len(inorder)) starts with the entire arrays and reconstructs the complete tree.

Example Walkthrough

Let's walk through a concrete example to understand how the algorithm reconstructs a binary tree.

Given:

• inorder = [9, 3, 15, 20, 7]
• postorder = [9, 15, 7, 20, 3]

Goal: Reconstruct the binary tree that produces these traversals.

Step 1: Initialize

• Create hash table: d = {9:0, 3:1, 15:2, 20:3, 7:4}
• Call dfs(0, 0, 5) to build the entire tree

Step 2: First call - dfs(0, 0, 5)

• Root value: postorder[0 + 5 - 1] = postorder[4] = 3
• Root position in inorder: k = d[3] = 1
• Left subtree size: k - i = 1 - 0 = 1 node
• Right subtree size: 5 - 1 + 0 - 1 = 3 nodes
• Build left subtree: dfs(0, 0, 1)
• Build right subtree: dfs(2, 1, 3)

Step 3: Left subtree - dfs(0, 0, 1)

• Root value: postorder[0 + 1 - 1] = postorder[0] = 9
• Root position in inorder: k = d[9] = 0
• Left subtree size: 0 - 0 = 0 (no left child)
• Right subtree size: 1 - 0 + 0 - 1 = 0 (no right child)
• Return: TreeNode(9)

Step 4: Right subtree - dfs(2, 1, 3)

• Root value: postorder[1 + 3 - 1] = postorder[3] = 20
• Root position in inorder: k = d[20] = 3
• Left subtree size: 3 - 2 = 1 node
• Right subtree size: 3 - 3 + 2 - 1 = 1 node
• Build left subtree: dfs(2, 1, 1)
• Build right subtree: dfs(4, 2, 1)

Step 5: Node 20's left child - dfs(2, 1, 1)

• Root value: postorder[1 + 1 - 1] = postorder[1] = 15
• Root position in inorder: k = d[15] = 2
• Left subtree size: 2 - 2 = 0 (no left child)
• Right subtree size: 1 - 2 + 2 - 1 = 0 (no right child)
• Return: TreeNode(15)

Step 6: Node 20's right child - dfs(4, 2, 1)

• Root value: postorder[2 + 1 - 1] = postorder[2] = 7
• Root position in inorder: k = d[7] = 4
• Left subtree size: 4 - 4 = 0 (no left child)
• Right subtree size: 1 - 4 + 4 - 1 = 0 (no right child)
• Return: TreeNode(7)

Step 7: Assemble the tree The recursion unwinds and builds:

       3
      / \
     9   20
        /  \
       15   7

Each recursive call identifies its root from postorder's last element, uses the hash table to split the inorder array, and recursively builds its subtrees using the calculated boundaries.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm constructs a binary tree from inorder and postorder traversals. Breaking down the operations:

• Creating the dictionary d from the inorder list takes O(n) time, where we iterate through all n elements once
• The recursive function dfs visits each node exactly once during tree construction
• At each node, we perform constant time operations: finding the root value from postorder (O(1)), looking up its index in the dictionary (O(1)), and creating a TreeNode (O(1))
• The recursive calls partition the problem into left and right subtrees without overlap, ensuring each element is processed exactly once

Therefore, the total time complexity is O(n).

Space Complexity: O(n)

The space usage consists of:

• The dictionary d storing the index mapping of all n elements from the inorder traversal: O(n)
• The recursion call stack depth, which in the worst case (skewed tree) can go up to O(n), and in the best case (balanced tree) would be O(log n)
• The output tree structure itself contains n nodes: O(n)

Since we need to account for the worst case and the dominant factors, the overall space complexity is O(n).

Common Pitfalls

1. Incorrect Index Calculation for Right Subtree in Postorder Array

One of the most common mistakes is incorrectly calculating the starting index for the right subtree in the postorder array.

The Pitfall: Developers often mistakenly use postorder_start + left_subtree_size + 1 as the starting index for the right subtree in postorder, thinking they need to skip the root element. However, the root is at the END of the postorder segment, not after the left subtree.

Incorrect Implementation:

# WRONG: This incorrectly skips an extra element
right_child = build_subtree(
    root_inorder_idx + 1,
    postorder_start + left_subtree_size + 1,  # ❌ Wrong!
    subtree_size - left_subtree_size - 1
)

Correct Implementation:

# CORRECT: Right subtree starts immediately after left subtree in postorder
right_child = build_subtree(
    root_inorder_idx + 1,
    postorder_start + left_subtree_size,  # ✓ Correct!
    subtree_size - left_subtree_size - 1
)

Why This Happens: In postorder traversal, the sequence is: [left subtree] [right subtree] [root]. The root is the LAST element at index postorder_start + subtree_size - 1, not in the middle. Therefore:

• Left subtree: indices [postorder_start, postorder_start + left_subtree_size)
• Right subtree: indices [postorder_start + left_subtree_size, postorder_start + subtree_size - 1)
• Root: index postorder_start + subtree_size - 1

2. Handling Duplicate Values

The Pitfall: The algorithm assumes all node values are unique. If the tree contains duplicate values, the hash map will overwrite indices, leading to incorrect tree reconstruction.

Example Problem:

inorder = [2, 2, 3]
postorder = [2, 3, 2]
# The hash map becomes {2: 1, 3: 2}, losing the first occurrence of 2

Solution: Either ensure input constraints specify unique values, or modify the approach to handle duplicates by using a different strategy (like maintaining a pointer instead of using a hash map).

3. Off-by-One Errors in Subtree Size Calculation

The Pitfall: Forgetting to subtract 1 when calculating the right subtree size, since we need to exclude the root node.

Incorrect:

right_subtree_size = subtree_size - left_subtree_size  # ❌ Includes root

Correct:

right_subtree_size = subtree_size - left_subtree_size - 1  # ✓ Excludes root

Debugging Tip: To avoid these index errors, it helps to trace through a small example manually or add assertions to verify that indices stay within bounds:

assert postorder_start + subtree_size - 1 < len(postorder), "Root index out of bounds"
assert left_subtree_size >= 0, "Invalid left subtree size"