algoadvance

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.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.

Clarifying Questions

1. Q: Are duplicates allowed in the input arrays?
   • A: No, both inorder and postorder consist of unique values.
2. Q: Should we assume that the input arrays are valid and represent a binary tree?
   • A: Yes, the input arrays are always valid and represent a binary tree.
3. Q: What should be returned?
   • A: We should return the root of the constructed binary tree.

Strategy

To build the binary tree from inorder and postorder traversals, we can use the following strategy:

1. Identify the root: The last element in the postorder list is the root of the tree.
2. Partition the inorder list: Once the root is identified, partition the inorder list into left and right subtrees using the root’s index.
3. Recursively construct subtrees: Use the partitions of the inorder list to recursively construct the left and right subtrees.

Steps:

1. Create a mapping from values to their indices in the inorder array to quickly locate the root and partition indices.
2. Recursively build the tree by popping elements from the end of the postorder list and partitioning the inorder array accordingly.

Code

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None

    # Mapping of inorder values to their indices for quick lookup
    inorder_index_map = {value: idx for idx, value in enumerate(inorder)}
    
    def helper(in_left, in_right):
        if in_left > in_right:
            return None
        
        # The last element in postorder is the root of the current tree
        root_val = postorder.pop()
        root = TreeNode(root_val)
        
        # Split the inorder list into left and right subtrees
        index = inorder_index_map[root_val]
        
        # Recursively construct the right subtree
        root.right = helper(index + 1, in_right)
        # Recursively construct the left subtree
        root.left = helper(in_left, index - 1)
        
        return root

    # Start with the full range of the inorder list
    return helper(0, len(inorder) - 1)

# Example Usage
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
tree = buildTree(inorder, postorder)

Time Complexity

• Time Complexity: O(n)
  • Each node is processed exactly once.
  • Building the index map of the inorder array is O(n).
  • Recursively constructing the tree for each element is O(n).
• Space Complexity: O(n)
  • The space used for the index map is O(n).
  • The recursion stack could go as deep as the tree height which, in the worst case (like a skewed tree), is O(n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?