105. Construct Binary Tree from Preorder and Inorder Traversal

Medium

Problem:

Given the preorder and inorder traversal results of a tree as input, construct the binary tree.

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

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

Solution:

There are primarily three types of tree traversals: preorder, inorder, and postorder. With just any two of these traversals, a binary tree can be restored.

The first value in the preorder is the parent node. In other words, the first result of the preorder traversal precisely divides the inorder traversal result into left and right. Essentially, this converts the problem into a divide-and-conquer based on inorder traversal.

# 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
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if inorder:
            mid = inorder.index(preorder.pop(0))

            # Divde and Conquer
            node = TreeNode(inorder[mid])
            node.left = self.buildTree(preorder, inorder[:mid])
            node.right = self.buildTree(preorder, inorder[mid + 1:])

            return node

Note: In Python, the list can take an index for the pop() function, essentially performing the roles of both a stack and a queue. However, using pop(0) has a time complexity of $O(n)$.