🌳105. Construct Binary Tree from Preorder and Inorder Traversal

Grind 75 | Medium | Monday 10th April, 2023

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Constraints:

• 1 <= preorder.length <= 3000

• inorder.length == preorder.length

• -3000 <= preorder[i], inorder[i] <= 3000

• preorder and inorder consist of unique values.

• Each value of inorder also appears in preorder.

• preorder is guaranteed to be the preorder traversal of the tree.

• inorder is guaranteed to be the inorder traversal of the tree.

Example 1

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

Example 2

Input: preorder = [-1], inorder = [-1]
Output: [-1]

SOLUTION

The order in which you visit nodes for each traversal. Preorder: root node -> left subtree -> right subtree Inorder: left subtree -> root node -> right subtree

To reconstruct a binary tree from its preorder and inorder traversals, we can start by identifying the root node. Note that the root node is always the first node in the preorder list. We then find the index of the root node in the inorder list. This tells us the boundaries of the left and right subtrees for the root node. All the nodes to the left of the root node belong to the left subtree, and all the nodes to the right of the root node belong to the right subtree.

We iterate over the preorder list and pop each element until there are no more elements. For each popped element, we find its index in the inorder list, which tells us the boundaries of the left and right subtrees for the current element. We then recursively build the left and right subtrees for the current element. To do this, we pass the preorder list and a sublist of the inorder list that corresponds to the current subtree to the recursive function. By recursively building the left and right subtrees for each element in the preorder list, we can reconstruct the entire binary tree.

# 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]:
        def recurse(preorder, inorder):
            # no more nodes to traverse so return none
            if not inorder: 
                return 

            # pop last element since we reversed the list.
            value       = preorder.pop()
            # create the node with the current value
            curr_node   = TreeNode(value)
            # need the index to partition the inorder into left and right subtree 
            index       = inorder.index(value)

            # left subtree will be the elements left to current element in inorder list
            curr_node.left  = recurse(preorder, inorder[:index])
            # right subtree will be the elements right to current element in inorder list
            curr_node.right = recurse(preorder, inorder[index+1:])

            return curr_node 

        # reverse the pre-order traversal to allow for easy popping of the root nodes
        preorder.reverse()
        return recurse(preorder, inorder)
        

TIME AND SPACE COMPLEXITY

TIME: O(n^2), where n is the number of nodes in the binary tree. This is because of the inorder.index() method used to find the index of the root node in the in-order traversal takes O(n) time in the worst case. The recurse function is called once for each node in the binary tree, and each call takes O(n) time to search for the inorder index. Therefore, the overall time complexity is O(n^2).

SPACE: O(n), where n is the number of nodes in the binary tree. We build a tree with n nodes.

***written with help from ChatGPT