We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct Binary Tree from Inorder and Postorder Traversal

Difficulty: Medium

Problem Description

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Key Insights

  • The last element of the postorder array is the root of the tree.
  • The inorder array can be used to determine the left and right subtrees.
  • Recursion can be used to build the tree from the bottom up.
  • We can use a hashmap to quickly find the index of elements in the inorder array.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree (length of the inorder and postorder arrays). Space Complexity: O(n), for the hashmap and the recursion stack.

Solution

To solve this problem, we can use a recursive approach. We start by identifying the root of the tree using the last element of the postorder array. We then find the index of this root in the inorder array, which allows us to determine the elements that belong to the left and right subtrees.

We create a hashmap to store the indices of the elements in the inorder array for O(1) access time. We recursively construct the left and right subtrees using the identified segments of the inorder and postorder arrays. The process is repeated until we have constructed the entire tree.

Code Solutions

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None
    
    # Create a hashmap to store the indices of inorder elements
    inorder_index_map = {value: index for index, value in enumerate(inorder)}
    
    def constructTree(in_left, in_right, post_left, post_right):
        if in_left > in_right or post_left > post_right:
            return None
        
        # The last element in postorder is the root
        root_val = postorder[post_right]
        root = TreeNode(root_val)
        
        # Find the root index in inorder array
        root_index = inorder_index_map[root_val]
        
        # Calculate the size of the left subtree
        left_tree_size = root_index - in_left
        
        # Recursively build the left and right subtrees
        root.left = constructTree(in_left, root_index - 1, post_left, post_left + left_tree_size - 1)
        root.right = constructTree(root_index + 1, in_right, post_left + left_tree_size, post_right - 1)
        
        return root
    
    return constructTree(0, len(inorder) - 1, 0, len(postorder) - 1)
← Back to All Questions