[Top Interview 150] 105. Construct Binary Tree from Preorder and Inorder Travers

Solution)

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # Base Case
        if not preorder or not inorder:
            return None
        
        # Root of a tree
        root = TreeNode(preorder[0])
        
        # Index of root to distinguish left/right subtrees
        mid = inorder.index(preorder[0])

        # Recursive calls to build left/right subtrees using mid
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])

        return root

 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n^2)
Time Complexity: O(n^2)
 

Explanation)

This solution is from NeetCode's solution, so check his video as well!
 
This solution executes recursions using sliced lists. These sliced lists each denotes the nodes in left and right subtrees. 
 
The range of left and right subtrees is determined by finding the index of the root node in inorder traversal.
 
- In preorder, we know the 0th element is always the root node.
- In inorder, we know the left range of the root node is the left subtree, and the right range of the root node is the right subtree.
 

How to find left/right subtrees

 

1. Base Case)

If preorder and inorder traversals do not exist, there is nothing to return so we return None.
 

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

 

2. root node and its index)

As said earlier, we know that the 0th element in preorder is always the root of a tree.
So we'll make that our root node.
 
Then to determine which node is on the left/right side of root, we need to find the index of the root node in inorder.
Once we find that, we know how many nodes are on the left/right side of root.
 

How many nodes are on the left/right side of root

  

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

 

3. Recursive calls)

Now that we know the nodes in left/right subtrees, we can put those nodes into each subtree.
 
Send those nodes by slicing preorder and inorder traversals. Slice the traversals using the index mid.
By recursively slicing the traversals, we'll eventually have empty traversals. At that point we've assigned all the nodes to their proper positions.
 
After all the recursions, return root.
 

def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # 1. Base Case
        if not preorder or not inorder:
            return None
           
        # 2. root node and its index
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])
        
        # 3. Recursive calls
        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])

        return root

 
 
 
I realized I needed to use root node and its index, but didn't know how to do it using recursion. I can already see myself watching NeetCode for the rest of the problems in this topic :(