LeetCode Solutions Blog

Construct Binary Tree from Inorder and Postorder Traversal

Number: 106

Difficulty: Medium

Paid? No

Problem Description

Given the inorder and postorder traversal arrays of a binary tree (with unique node values), construct and return the binary tree.

Key Insights

The last element of the postorder array is always the root.
Finding the index of the root in the inorder array splits the tree into left and right subtrees.
Recursively reconstruct the tree using the divided inorder arrays and corresponding segments of the postorder array.
Use a hash table (or dictionary) to quickly locate the index of any value in the inorder array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (Space is used for the recursive call stack and extra hash table)

Solution

We can solve the problem by leveraging the observation that in postorder traversal, the last element is the root of the current subtree. After identifying the root, we locate its index in the inorder array which partitions the array into left and right subtrees. A hash table is used for fast lookup of the root index in the inorder sequence. We then recursively apply the same process for left and right subtrees, carefully managing indices to maintain alignment between the inorder and postorder arrays.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val         # Node's value
        self.left = left       # Left child
        self.right = right     # Right child

class Solution:
    def buildTree(self, inorder: list[int], postorder: list[int]) -> TreeNode:
        # Create a dictionary to map value -> index in the inorder array for O(1) lookup
        inorder_index_map = {value: idx for idx, value in enumerate(inorder)}
        
        # Recursive helper function that builds the tree
        def build(left_in, right_in, left_post, right_post):
            if left_in > right_in or left_post > right_post:
                return None
                
            # Last element in current postorder range is root
            root_val = postorder[right_post]
            root = TreeNode(root_val)
            
            # Find the index of the root in inorder traversal
            index = inorder_index_map[root_val]
            # Number of nodes in left subtree
            left_count = index - left_in
            
            # Construct left subtree using the corresponding subarrays
            root.left = build(left_in, index - 1, left_post, left_post + left_count - 1)
            # Construct right subtree using the corresponding subarrays
            root.right = build(index + 1, right_in, left_post + left_count, right_post - 1)
            
            return root
        
        # Initiate the recursive function with proper indices
        return build(0, len(inorder) - 1, 0, len(postorder) - 1)
        
# Example usage:
# sol = Solution()
# tree = sol.buildTree([9,3,15,20,7], [9,15,7,20,3])