Construct Binary Tree from Preorder and Inorder Traversal

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. For example:

Example 1:

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

In this case, the output should be a binary tree represented as [3,9,20,null,null,15,7]. In other words, the tree's root is 3, the left child of 3 is 9, and the right child of 3 is 20. 20 has a left child of 15 and a right child of 7.

Example 2:

preorder = [-1], inorder = [-1]

In this case, the output should be a binary tree represented as [-1]. In other words, there is a single node in the tree and its value is -1.

Write a function that takes the preorder and inorder arrays as input and returns the root of the constructed binary tree. The tree should be built according to the given traversals. The values in the input arrays are guaranteed to be unique.

# 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]) -> TreeNode:
        if not preorder or not inorder:
            return None

        # The first element in preorder is always the root.
        root_val = preorder[0]
        root = TreeNode(root_val)

        # Find the index of the root value in inorder.
        root_index_inorder = inorder.index(root_val)

        # The left subtree is all elements in inorder to the left of root.
        # The right subtree is all elements in inorder to the right of root.
        # We use the inorder indices to split preorder as well.
        root.left = self.buildTree(
            preorder[1 : root_index_inorder + 1],
            inorder[:root_index_inorder],
        )
        root.right = self.buildTree(
            preorder[root_index_inorder + 1 :],
            inorder[root_index_inorder + 1 :],
        )

        return root

# Example Usage
# Create an instance of the Solution class
solution = Solution()

# Example 1
preorder1 = [3, 9, 20, 15, 7]
inorder1 = [9, 3, 15, 20, 7]
tree1 = solution.buildTree(preorder1, inorder1)
# (Visualization or further processing of tree1 would be needed here)

# Example 2
preorder2 = [-1]
inorder2 = [-1]
tree2 = solution.buildTree(preorder2, inorder2)
# (Visualization or further processing of tree2 would be needed here)

Explanation:

1. TreeNode Class: Defines the structure for a node in a binary tree.
2. buildTree(preorder, inorder) Function: This function constructs the binary tree.
   • Base Case: If either preorder or inorder is empty, it means we've reached the end of a branch, so we return None.
   • Root Creation: The first element of preorder is the root of the current (sub)tree. We create a new TreeNode with this value.
   • Finding the Root in inorder: We find the index of the root's value in the inorder list. This index helps us divide the inorder list into left and right subtrees.
   • Recursive Calls: We then recursively call buildTree for the left and right subtrees.
     • For the left subtree, we pass the portion of preorder and inorder that corresponds to the left subtree.
     • For the right subtree, we pass the portion of preorder and inorder that corresponds to the right subtree.
   • Returning the Root: Finally, the function returns the root of the constructed tree.

Illustration

Consider preorder = [3, 9, 20, 15, 7] and inorder = [9, 3, 15, 20, 7]

1. The first element of preorder (3) is the root.
2. Search for 3 in inorder. The elements to the left of 3 (i.e., 9) form the left subtree, and the elements to the right of 3 (i.e., 15, 20, 7) form the right subtree.
3. Recursively apply these steps to the left and right subtrees.

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes in the tree. The function processes each node once. The inorder.index() operation takes O(n) time in the worst case, but amortized over the entire execution, it can be considered O(1) on average due to the uniqueness constraint.
• Space Complexity: O(n) in the worst case, due to the call stack during recursion. The depth of the recursion can be n in the case of a skewed tree.

Edge Cases:

• Empty Input Lists: If either preorder or inorder is empty, the function correctly returns None.
• Single Node: If both lists contain only one element, the function correctly creates a tree with a single node.
• Duplicate Values: The problem statement specifies that values are unique, so no special handling is needed for duplicate values. If duplicates were allowed, the inorder.index() method would need to be handled carefully as it only returns the first occurrence.
• Invalid Input: If preorder and inorder do not represent the same tree structure (e.g., they have different lengths or contain different values), the resulting tree may not be correct. However, the function will still execute without error (assuming the value in preorder[0] exists in inorder).

Brute Force Approach (Less Efficient):

A naive approach would be to iterate through the inorder array in each recursive call to find the index of the root. This would increase the time complexity as described below.

Optimal Solution

The provided solution is already optimized in terms of algorithmic complexity for this problem, adhering to O(n) time complexity given the constraints.