105. Construct Binary Tree from Preorder and Inorder Traversal

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

Example

---

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

💻 Code

Approach :

          root
preorder = [3,  9,  20,  15,  7]

inorder  = [9,  3,  15,  20,  7]
            |       |_________|
           left        right

• preorder: increasing by 1, which is the current parent
• inorder: current index splits for left & right subtrees

1. Brute Force

---

• TC : $O(n^2)$
  • Recursion: $O(n)$
  • list.index(int) : $O(n)$
• SC: $O(n)$

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # base case
        if not preorder or not inorder:
            return None

        # set the current first node of preorder as a root
        root_val = preorder[0]
        root = TreeNode(root_val)

        # recognize where we split in left & right
        mid = inorder.index(root_val)
        
        # in preorder, the first index will always be a root
        # the current index in inorder will be increased if there are more left node
        # thus, left: [1:mid + 1], right: [mid + 1:]
        # split except the current parent node (inorder)
        root.left = self.buildTree(preorder[1:mid + 1], inorder[:mid])
        root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])

        return root

The above recursion method identifies the next parent node and connects with its children. The gist of it is figuring out how the components of preorder and inorder represent when it is converted to a tree.

The inefficiency of this method is accessing the current parent point of the inorder since it uses index() function. This searches index traversing an array from index 0, which means $O(n)$. Since this is a recursion the time complexity will be $O(n^2)$.

Since we create a new tree with arrays, the Space Complexity has to be $O(n)$.

2. Optimised Solution

---

✅ Hash map

• TC : $O(n)$
  • Recursion: $O(n)$
  • hash map : $O(1)$
• SC: $O(n)$

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # {9: 0, 3: 1, 15: 2, 20: 3, 7: 4}
        # this takes O(n), but outside of the recursion.
        inorder_map = {val: idx for idx, val in enumerate(inorder)}
        
        # set a global reference so that we can access the current parent node.
        pre_idx = [0]

        def build(in_start, in_end):
            if in_start > in_end:
                return None

            root_val = predorder[pre_idx[0]]
            pre_idx[0] += 1
            root = TreeNode(root_val)
            
            # Using map, O(1)!!
            mid = inorder_map[root_val]

            root.left = build(in_start, mid - 1)
            root.right = build(mid + 1, in_end)

            return root
        
        return build(0, len(inorder) - 1)