Problem Description

You are given two integer arrays representing tree traversals:

• preorder: the preorder traversal of a binary tree with distinct values
• postorder: the postorder traversal of the same binary tree

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

Key Points:

• All values in the tree are distinct (no duplicates)
• Both arrays represent the same binary tree
• If multiple valid trees can be constructed from the given traversals, you may return any one of them

Understanding the Traversals:

• Preorder traversal visits nodes in this order: root → left subtree → right subtree
• Postorder traversal visits nodes in this order: left subtree → right subtree → root

For example, if you have a tree:

      1
     / \
    2   3

• Preorder would be: [1, 2, 3]
• Postorder would be: [2, 3, 1]

The challenge is to use the properties of these two traversal orders to uniquely identify the structure of the tree and reconstruct it. Since the root appears first in preorder and last in postorder, you can identify the root. The subtrees can then be determined by finding where the left subtree's root (second element in preorder) appears in the postorder array, which helps partition the arrays into left and right subtree segments.

Intuition

Let's think about what we know from the two traversal patterns:

In preorder, the first element is always the root. The pattern is [root, ...left subtree..., ...right subtree...].

In postorder, the last element is always the root. The pattern is [...left subtree..., ...right subtree..., root].

This immediately tells us that preorder[0] is our root node, and it matches postorder[-1].

Now comes the key insight: How do we find where the left subtree ends and the right subtree begins?

If the tree has a left subtree, then preorder[1] must be the root of the left subtree (since preorder visits root → left → right). We can find this value in the postorder array. Here's why this is useful:

In postorder, the root of the left subtree appears at the end of the left subtree section. So if we find preorder[1] in postorder at index i, then:

• Elements from postorder[0] to postorder[i] form the left subtree
• Elements from postorder[i+1] to postorder[-2] form the right subtree (excluding the main root at postorder[-1])

Once we know the size of the left subtree (let's call it m), we can partition both arrays:

• In preorder: left subtree is preorder[1:1+m], right subtree is preorder[1+m:]
• In postorder: left subtree is postorder[0:m], right subtree is postorder[m:-1]

This naturally leads to a recursive solution: we can apply the same logic to each subtree, treating each subtree's portion of the arrays as a smaller version of the original problem.

The base cases are straightforward:

• If the array is empty, return None
• If the array has one element, return a leaf node

To optimize lookups, we can precompute a hashmap that stores each value's position in the postorder array, allowing us to find the left subtree root's position in O(1) time instead of O(n).

Learn more about Tree, Divide and Conquer and Binary Tree patterns.

Solution Approach

The solution uses a recursive approach with a helper function dfs(a, b, c, d) where:

• [a, b] represents the current range in the preorder array
• [c, d] represents the current range in the postorder array

Step 1: Create a Position HashMap

First, we build a hashmap pos that stores each value's index in the postorder array:

pos = {x: i for i, x in enumerate(postorder)}

This allows O(1) lookups when we need to find where a value appears in postorder.

Step 2: Implement the Recursive Function

The dfs function works as follows:

1. Base Case - Empty Range: If a > b, the range is empty, return None.

2. Create Root Node: The root is always at preorder[a]:

   root = TreeNode(preorder[a])

3. Base Case - Single Node: If a == b, this is a leaf node with no children, return the root directly.

4. Find Left Subtree Boundary:

   • The left subtree's root (if it exists) is preorder[a + 1]
   • Find its position in postorder: i = pos[preorder[a + 1]]
   • Calculate the number of nodes in left subtree: m = i - c + 1

   This works because in postorder, all nodes of the left subtree appear before its root at position i.

5. Recursively Build Subtrees:

   • Left subtree:
     • Preorder range: [a + 1, a + m] (skip root, take next m elements)
     • Postorder range: [c, i] (from start to left subtree root)
   • Right subtree:
     • Preorder range: [a + m + 1, b] (skip root and left subtree)
     • Postorder range: [i + 1, d - 1] (after left subtree, exclude main root)

   root.left = dfs(a + 1, a + m, c, i)
   root.right = dfs(a + m + 1, b, i + 1, d - 1)

6. Return the constructed tree: Return the root with its attached subtrees.

Step 3: Initial Call

Start the recursion with the full range of both arrays:

return dfs(0, len(preorder) - 1, 0, len(postorder) - 1)

Time Complexity: O(n) where n is the number of nodes, as each node is processed once.

Space Complexity: O(n) for the hashmap and the recursion stack in the worst case (skewed tree).

The elegance of this solution lies in using the properties of preorder and postorder traversals to identify subtree boundaries without ambiguity, leveraging the fact that all values are distinct.

Example Walkthrough

Let's walk through the algorithm with a concrete example to see how it reconstructs the tree.

Given:

• preorder = [1, 2, 4, 5, 3, 6]
• postorder = [4, 5, 2, 6, 3, 1]

Step 1: Build the position hashmap

pos = {4: 0, 5: 1, 2: 2, 6: 3, 3: 4, 1: 5}

Step 2: Initial call to dfs(0, 5, 0, 5)

First recursive call (entire tree):

• Range: preorder[0:5], postorder[0:5]
• Root = preorder[0] = 1
• Left subtree root candidate = preorder[1] = 2
• Find 2 in postorder: pos[2] = 2
• Left subtree size m = 2 - 0 + 1 = 3
• Split:
  • Left subtree: dfs(1, 3, 0, 2) → preorder[1:3]=[2,4,5], postorder[0:2]=[4,5,2]
  • Right subtree: dfs(4, 5, 3, 4) → preorder[4:5]=[3,6], postorder[3:4]=[6,3]

Second recursive call (left subtree of 1):

• Range: preorder[1:3], postorder[0:2]
• Root = preorder[1] = 2
• Left subtree root candidate = preorder[2] = 4
• Find 4 in postorder: pos[4] = 0
• Left subtree size m = 0 - 0 + 1 = 1
• Split:
  • Left subtree: dfs(2, 2, 0, 0) → preorder[2:2]=[4], postorder[0:0]=[4]
  • Right subtree: dfs(3, 3, 1, 1) → preorder[3:3]=[5], postorder[1:1]=[5]

Third recursive call (node 4):

• Single element, return TreeNode(4)

Fourth recursive call (node 5):

• Single element, return TreeNode(5)

Node 2 now has left child 4 and right child 5.

Fifth recursive call (right subtree of 1):

• Range: preorder[4:5], postorder[3:4]
• Root = preorder[4] = 3
• Left subtree root candidate = preorder[5] = 6
• Find 6 in postorder: pos[6] = 3
• Left subtree size m = 3 - 3 + 1 = 1
• Split:
  • Left subtree: dfs(5, 5, 3, 3) → preorder[5:5]=[6], postorder[3:3]=[6]
  • Right subtree: dfs(6, 5, 4, 3) → empty (since 6 > 5)

Sixth recursive call (node 6):

• Single element, return TreeNode(6)

Seventh recursive call (empty right subtree of 3):

• a > b, return None

Node 3 now has left child 6 and no right child.

Final Tree Structure:

      1
     / \
    2   3
   / \  /
  4  5 6

This matches our original traversals:

• Preorder (root→left→right): 1 → 2 → 4 → 5 → 3 → 6 ✓
• Postorder (left→right→root): 4 → 5 → 2 → 6 → 3 → 1 ✓

The key insight demonstrated here is how finding the left subtree root in postorder tells us exactly how many nodes belong to the left subtree, allowing us to correctly partition both arrays for recursive processing.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm constructs a binary tree from preorder and postorder traversals. Breaking down the time complexity:

1. Creating the pos dictionary takes O(n) time, where we iterate through all elements in the postorder array once.

2. The dfs function visits each node exactly once during the tree construction. For each node:

   • Creating a new TreeNode takes O(1) time
   • Looking up the position in the pos dictionary takes O(1) time
   • Calculating the split point takes O(1) time
   • Making recursive calls for left and right subtrees

Since each of the n nodes is processed exactly once with O(1) operations per node, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity consists of:

1. The pos dictionary storing positions of all n elements from the postorder array: O(n) space

2. The recursion call stack depth, which in the worst case (skewed tree) can go up to O(n) levels deep

3. The output tree structure itself contains n nodes: O(n) space

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

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Left Child Always Exists

The Pitfall: The most critical error in this solution is assuming that preorder[pre_start + 1] is always the left child. When a node has only a right child (no left child), preorder[pre_start + 1] would actually be the right child, not the left child. This assumption causes the algorithm to incorrectly partition the arrays and construct an invalid tree.

Example of Failure:

Tree:     1
           \
            2
             \
              3

Preorder:  [1, 2, 3]
Postorder: [3, 2, 1]

In this case, preorder[1] = 2 is the right child of 1, not the left child. The algorithm would incorrectly try to build 2 as the left child.

Solution: Check if the potential left child actually exists by verifying if it could be a left child:

def build_tree(pre_start, pre_end, post_start, post_end):
    if pre_start > pre_end:
        return None
  
    root = TreeNode(preorder[pre_start])
  
    if pre_start == pre_end:
        return root
  
    # Check if left child exists
    # If preorder[pre_start + 1] appears right before the root in postorder,
    # it means there's no left subtree (it's actually the right child)
    potential_left_val = preorder[pre_start + 1]
    potential_left_idx = postorder_index_map[potential_left_val]
  
    # If the potential left child is at post_end - 1, it's actually a right child
    if potential_left_idx == post_end - 1:
        # No left child, only right child
        root.right = build_tree(
            pre_start + 1, 
            pre_end, 
            post_start, 
            post_end - 1
        )
    else:
        # Normal case: has left child (and possibly right child)
        left_subtree_size = potential_left_idx - post_start + 1
      
        root.left = build_tree(
            pre_start + 1,
            pre_start + left_subtree_size,
            post_start,
            potential_left_idx
        )
      
        root.right = build_tree(
            pre_start + left_subtree_size + 1,
            pre_end,
            potential_left_idx + 1,
            post_end - 1
        )
  
    return root

2. Off-by-One Errors in Range Calculations

The Pitfall: Incorrectly calculating the boundaries for recursive calls, especially forgetting to exclude the root from postorder's right subtree range (post_end - 1 instead of post_end).

Solution: Always remember:

• In preorder: root is at the start of the range
• In postorder: root is at the end of the range
• Right subtree in postorder ends at post_end - 1 (excluding the current root)

3. Not Handling Edge Cases

The Pitfall: Forgetting to handle single-node trees or empty subtrees properly.

Solution: Always include both base cases:

• Empty range: if pre_start > pre_end: return None
• Single node: if pre_start == pre_end: return root

These checks prevent index out of bounds errors and ensure correct tree construction for all cases.