LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal Solution in Python Explained

Problem Statement

In LeetCode 106, you’re given two integer arrays: inorder (left, root, right) and postorder (left, right, root) traversals of a binary tree with unique values. Your task is to construct the binary tree and return its root. This complements LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal, using postorder instead of preorder, and differs from depth calculation like LeetCode 104: Maximum Depth of Binary Tree.

Constraints

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• Values are unique
• Arrays represent a valid tree

Example

Let’s see some cases:

Copy codeInput: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
      3
     / \
    9  20
       / \
      15  7
Explanation: Postorder ends with root (3), Inorder splits left (9) and right (15,20,7).

Copy codeInput: inorder = [1], postorder = [1]
Output: [1]
Explanation: Single node tree.

Copy codeInput: inorder = [2,1], postorder = [2,1]
Output: [1,2]
Explanation: Root 1, left 2.

These examples show we’re reconstructing a tree from traversals.

Understanding the Problem

How do you solve LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal in Python? Take inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]. Postorder ends with the root (3), and inorder splits at 3 into left (9) and right (15,20,7). Recursively build subtrees using these splits. This isn’t a zigzag traversal like LeetCode 103: Binary Tree Zigzag Level Order Traversal; it’s about tree construction from traversal data. We’ll use: 1. Recursive Construction with Hash Map: O(n) time, O(n) space—our best solution. 2. Recursive without Hash Map: O(n²) time, O(h) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive Construction with Hash Map Approach

Explanation

Recursive Construction with Hash Map uses postorder’s last element as the root and inorder to determine left and right subtrees. A hash map stores inorder indices for O(1) lookup, enabling efficient splitting. Recursively build the tree by adjusting indices. This is the best solution due to its O(n) time complexity, leveraging the hash map to avoid linear searches, making it both efficient and intuitive.

For inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]:

• Root: 3 (postorder[-1]), inorder index 1.
• Left: 9 (inorder[0:1]), Right: 15,20,7 (inorder[2:5]).
• Recurse on subarrays.

Step-by-Step Example

Assume a TreeNode class: class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

Goal: Return [3,9,20,null,null,15,7].

• Start: inorder_map = {9:0, 3:1, 15:2, 20:3, 7:4}, build(0, 5, 0, 5).
• Step 1: Root = postorder[4] = 3, in_idx = 1.
• Left size = 1 - 0 = 1.
• Left: build(0, 1, 0, 1).
• Root = 9, in_idx = 0, size = 0.
• Left: None, Right: None.
• Return 9.
• Right: build(1, 4, 2, 5).
• Root = 20, in_idx = 3, size = 1.
• Left: build(1, 2, 2, 3) → 15.
• Right: build(2, 3, 4, 5) → 7.
• Return 20->15->7.
• Return 3->9->20.
• Finish: [3,9,20,null,null,15,7].

Example 2: inorder = [1], postorder = [1]

Goal: Return [1].

• Start: inorder_map = {1:0}, build(0, 1, 0, 1).
• Step 1: Root = 1, in_idx = 0, size = 0.
• Left: None, Right: None.
• Finish: Return [1].

Example 3: inorder = [2,1], postorder = [2,1]

Goal: Return [1,2].

• Start: inorder_map = {2:0, 1:1}, build(0, 2, 0, 2).
• Step 1: Root = 1, in_idx = 1, size = 1.
• Left: build(0, 1, 0, 1) → 2.
• Right: None.
• Finish: Return [1,2].

How the Code Works (Recursive Construction with Hash Map) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(inorder: list[int], postorder: list[int]) -> TreeNode:
    # Line 1: Create hash map for inorder indices
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    # Maps values to indices (e.g., {9:0, 3:1, 15:2, 20:3, 7:4})
    # Enables O(1) lookup of root position

    # Line 2: Define recursive builder function
    def build(post_start: int, post_end: int, in_start: int, in_end: int) -> TreeNode:
        # post_start/end = postorder range, in_start/end = inorder range
        # e.g., (0, 5, 0, 5) for full tree

        # Line 3: Base case - no nodes to process
        if post_start >= post_end:
            # If range is empty (e.g., 0 >= 0), return None
            return None

        # Line 4: Get root value from postorder
        root_val = postorder[post_end - 1]
        # Last element is root (e.g., 3 at post_end-1=4)

        # Line 5: Create root node
        root = TreeNode(root_val)
        # New node with root value (e.g., 3)

        # Line 6: Find root index in inorder
        root_idx = inorder_map[root_val]
        # O(1) lookup (e.g., 3 → 1)

        # Line 7: Calculate left subtree size
        left_size = root_idx - in_start
        # Number of nodes in left subtree (e.g., 1 - 0 = 1)

        # Line 8: Recursively build left subtree
        root.left = build(post_start, post_start + left_size, in_start, root_idx)
        # Postorder: start to start+size (e.g., 0 to 1), Inorder: start to root_idx (e.g., 0 to 1)
        # e.g., builds node 9

        # Line 9: Recursively build right subtree
        root.right = build(post_start + left_size, post_end - 1, root_idx + 1, in_end)
        # Postorder: after left to end-1 (e.g., 1 to 4), Inorder: root_idx+1 to end (e.g., 2 to 5)
        # e.g., builds node 20 with 15, 7

        # Line 10: Return constructed subtree
        return root
        # Returns root of current subtree (e.g., 3->9->20)

    # Line 11: Start construction
    return build(0, len(postorder), 0, len(inorder))
    # Initiates with full range (e.g., 0, 5, 0, 5)
    # Returns root of constructed tree

This detailed breakdown clarifies how recursive construction with a hash map efficiently builds the tree.

Alternative: Recursive without Hash Map Approach

Explanation

Recursive without Hash Map finds the root in postorder (last element), searches for it in inorder to split left and right subtrees, and builds recursively without a hash map. It’s a straightforward alternative but slower due to O(n) searches in inorder.

For [9,3,15,20,7], [9,15,7,20,3]:

• Root 3, split at index 1.
• Left: 9, Right: 15,20,7.
• Recurse similarly.

Step-by-Step Example (Alternative)

For [9,3,15,20,7], [9,15,7,20,3]:

• Step 1: Root = 3, find 3 in inorder (index 1).
• Left: [9], Right: [15,20,7].
• Step 2: Left = 9, no children.
• Step 3: Right = 20, split [15,20,7] → 15, 7.
• Finish: [3,9,20,null,null,15,7].

How the Code Works (Recursive without Hash Map)

Copy codedef buildTreeNoHash(inorder: list[int], postorder: list[int]) -> TreeNode:
    if not postorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(root_val)
    root_idx = inorder.index(root_val)
    root.left = buildTreeNoHash(inorder[:root_idx], postorder[:root_idx])
    root.right = buildTreeNoHash(inorder[root_idx + 1:], postorder[root_idx:-1])
    return root

Complexity

• Recursive Construction with Hash Map:
• Time: O(n) – hash map enables O(1) lookups.
• Space: O(n) – hash map and recursion stack.
• Recursive without Hash Map:
• Time: O(n²) – O(n) search per node.
• Space: O(h) – recursion stack, h = height.

Efficiency Notes

Recursive Construction with Hash Map is the best solution with O(n) time and O(n) space, optimizing lookups—Recursive without Hash Map is O(n²) due to linear searches, making it a simpler but less efficient alternative.

Key Insights

• Postorder: Root last.
• Inorder: Splits subtrees.
• Hash Map: Speeds up indexing.

Additional Example

For inorder = [4,2,1,3], postorder = [4,2,3,1]:

• Goal: [1,2,3,4].
• Hash Map: Builds 1->2->4 (left), 3 (right).

Edge Cases

• Single Node: [1], [1] → [1].
• Right Skewed: [1,2,3], [3,2,1] → [1,null,2,null,3].
• Empty: [], [] → None.

Both solutions handle these well.

Final Thoughts

LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal in Python is an insightful tree-building challenge. The Recursive Construction with Hash Map solution stands out for its efficiency and clarity, while Recursive without Hash Map offers a simpler approach. Want more? Try LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal for a related task or LeetCode 94: Binary Tree Inorder Traversal for traversal basics. Ready to practice? Solve LeetCode 106 on LeetCode with [9,3,15,20,7] and [9,15,7,20,3], aiming for [3,9,20,null,null,15,7]—test your skills now!