Construct Binary Tree From Inorder And Postorder Traversal - Leetcode Solution

Problem Statement:

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree.

Example:

Inorder traversal: [9,3,15,20,7] Postorder traversal: [9,15,7,20,3]

Return the following binary tree:

  3
 / \
9  20
  /  \
 15   7

Solution Approach:

Inorder traversal follows the left, root, right sequence whereas postorder follows the left, right, root sequence. From the postorder, we can find the root of the tree and then use that to divide the inorder array into left and right subtrees.

We can create a recursive function that takes in the two arrays and builds the tree recursively. The function can start by finding the root from the postorder array and then searching for the root in the inorder array. All elements to the left of the root in the inorder array can be used to build the left subtree and all elements to the right of the root in the inorder array can be used to build the right subtree.

Once the left and right subtrees are built, they can be attached to the root to create the final binary tree. The function can be recursively called with the left and right subtrees to build the complete binary tree.

Solution:

Here's the Python solution for the problem:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder or not postorder:
            return None
        
        root_val = postorder.pop()
        root = TreeNode(root_val)
        
        idx = inorder.index(root_val)
        
        root.right = self.buildTree(inorder[idx+1:], postorder)
        root.left = self.buildTree(inorder[:idx], postorder)
        
        return root

The above solution has a time complexity of O(n^2) since the index method used on lists with multiple same values takes O(n) time. We can improve the performance by using a hash map to store the index of each element in the inorder array, thus reducing the time complexity to O(n).

Here's the optimized Python solution:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        inorder_map = {}
        for i, val in enumerate(inorder):
            inorder_map[val] = i
        
        def helper(inorder, postorder, in_start, in_end, post_start, post_end):
            if in_start > in_end or post_start > post_end:
                return None
            
            root_val = postorder[post_end]
            root = TreeNode(root_val)
            
            idx = inorder_map[root_val]
            left_size = idx - in_start
            
            root.left = helper(inorder, postorder, in_start, idx-1, post_start, post_start+left_size-1)
            root.right = helper(inorder, postorder, idx+1, in_end, post_start+left_size, post_end-1)
            
            return root
        
        return helper(inorder, postorder, 0, len(inorder)-1, 0, len(postorder)-1)

The above solution has a time complexity of O(n) and a space complexity of O(n).

1