[Top Interview 150] 106. Construct Binary Tree from Inorder and Postorder Traver

Solution)

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # Base Case
        if not inorder or not postorder:
            return None
        
        # root is always the -1st element of postorder
        root = TreeNode(postorder[-1])
        # Find the index of root in inorder
        mid = inorder.index(postorder[-1])

        # Recursive Calls:
        # Adjust the ranges of left/right subtrees using mid
        root.left = self.buildTree(inorder[:mid], postorder[:mid])
        root.right = self.buildTree(inorder[mid+1:], postorder[mid:-1])

        return root

 
Problem: LeetCode
 
Time Complexity: O(n^2)
Space Complexity: O(n^2)
 

Explanation)

Find the root of the tree.
Then find the index of the root in inorder traversal.
 
Use that index to recursively slice the traversals. By recursively slicing the traversals, we can repeat the process of finding the roots of subtrees and attaching children.
 

1. Base Case)

As always, we'll need a base case of when the traversals are empty. Even though we know there will alwyas be at least one element in the traversals, it's handy to deal with recursions using such base cases.
 

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 1. Base Case
        if not inorder or not postorder:
            return None

 

2. Find the root and its index)

We need to find the root of the binary tree.
 
Postorder traversal's order goes from left => right => parent.
Thus we know that the root of the binary tree will always be at the end of the postorder traversal.
 
Once we have the root, find the index of it in inorder. The index in inorder becomes handy because we then know which nodes are on the left/right of the root.
 

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 1. Base Case
        if not inorder or not postorder:
            return None
        
        # 2. Find the root and its index
        root = TreeNode(postorder[-1])
        mid = inorder.index(postorder[-1])

 

3. Recursive Calls)

Now that we know which nodes belong to left/right subtrees, we'll assign them using slicing.
(If you don't understand why we slice as below, try comparing it with the actual inorder and postorder traversals)
 

def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 1. Base Case
        
        # 2. Find the root and its index
        root = TreeNode(postorder[-1])
        mid = inorder.index(postorder[-1])

        # 3. Recursive Calls
        root.left = self.buildTree(inorder[:mid], postorder[:mid])
        root.right = self.buildTree(inorder[mid+1:], postorder[mid:-1])

        return root

 
 
 
This problem was basically the same as the previous problem. If you knew the difference between postorder and preorder, solving it wouldn't be much of a problem.