Construct Binary Tree from Preorder and Inorder Traversal Interview Question for Meta

# 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:
        """Builds a binary tree from preorder and inorder traversals.

        Args:
            preorder (list[int]): The preorder traversal of the tree.
            inorder (list[int]): The inorder traversal of the tree.

        Returns:
            TreeNode: The root of the constructed binary tree.
        """
        if not preorder or not inorder:
            return None

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

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

        # Divide inorder array into left and right subtrees.
        inorder_left = inorder[:root_index_inorder]
        inorder_right = inorder[root_index_inorder + 1:]

        # Divide preorder array into left and right subtrees.
        preorder_left = preorder[1:len(inorder_left) + 1]
        preorder_right = preorder[len(inorder_left) + 1:]

        # Recursively build the left and right subtrees.
        root.left = self.buildTree(preorder_left, inorder_left)
        root.right = self.buildTree(preorder_right, inorder_right)

        return root

# Example Usage:
# preorder = [3,9,20,15,7]
# inorder = [9,3,15,20,7]
# solution = Solution()
# root = solution.buildTree(preorder, inorder)

# Visual representation of the constructed tree for the example:
#       3
#      / \
#     9  20
#       /  \
#      15   7

# Naive Approach:
# A naive approach would involve iterating through all possible tree structures
# and checking if their preorder and inorder traversals match the given arrays.
# This approach has an extremely high time complexity and is not practical.

# Optimal Approach:
# The optimal approach uses recursion to divide the problem into smaller subproblems.
# It leverages the properties of preorder and inorder traversals to identify the root,
# left subtree, and right subtree in each recursive step.

# Explanation:
# 1. The first element of the preorder traversal is always the root of the tree.
# 2. The inorder traversal has the property that all elements to the left of the root
#    belong to the left subtree, and all elements to the right of the root belong
#    to the right subtree.
# 3. We can use these properties to recursively build the tree by:
#    - Creating the root node using the first element of the preorder traversal.
#    - Finding the index of the root node in the inorder traversal.
#    - Dividing the inorder traversal into left and right subtrees based on the root index.
#    - Dividing the preorder traversal into left and right subtrees based on the size
#      of the left subtree in the inorder traversal.
#    - Recursively building the left and right subtrees using the divided traversals.

# Time and Space Complexity:
# Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited once.
# Space Complexity: O(N), in the worst case (skewed tree), due to the recursion stack. O(log N) for balanced tree.

Code Explanation

The code defines a TreeNode class representing a node in a binary tree, and a Solution class with a buildTree method that constructs a binary tree from its preorder and inorder traversals.

TreeNode Class: Defines the structure of a binary tree node with a value (val), a left child (left), and a right child (right).
buildTree Method:
- Takes the preorder and inorder lists as input.
- Handles the base case: If either preorder or inorder is empty, it means there's no tree to build, so it returns None.
- Creates the root node: The first element in the preorder list is always the root of the tree. A new TreeNode is created with this value.
- Finds the root's index in inorder: The index() method is used to find the index of the root's value in the inorder list. This index is crucial for splitting the inorder list into left and right subtrees.
- Divides inorder into left and right subtrees: Slices of the inorder list are created based on the root's index. inorder_left contains the nodes in the left subtree, and inorder_right contains the nodes in the right subtree.
- Divides preorder into left and right subtrees: Slices of the preorder list are created. The left subtree's preorder traversal (preorder_left) starts after the root in the preorder list and has the same length as the inorder_left list. The right subtree's preorder traversal (preorder_right) consists of the remaining elements in the preorder list.
- Recursively builds subtrees: The buildTree method is called recursively for the left and right subtrees, using the corresponding preorder and inorder slices.
- Connects subtrees to the root: The left and right attributes of the root node are set to the roots of the left and right subtrees returned by the recursive calls.
- Returns the root: The root of the constructed tree is returned.

Big O Runtime Analysis

The buildTree function has a time complexity of O(N), where N is the number of nodes in the tree. This is because each node is visited and processed exactly once. The index() method contributes a potential O(N) cost in the worst case for each recursive call. However, in practice, this is often amortized. Using a dictionary (hash map) to store the indices of inorder elements would reduce the time complexity of the index lookup to O(1), making the overall algorithm more efficient.

Big O Space Usage Analysis

The space complexity is O(N) in the worst case (skewed tree) due to the recursion stack. In the best case (balanced tree), the space complexity is O(log N). Additionally, O(N) space is used to store the tree itself. If a dictionary is used to store the indices of inorder elements, it would contribute an additional O(N) space.

Edge Cases

Empty Tree: If both preorder and inorder are empty, the function correctly returns None.
Single Node Tree: If both lists contain only one element, the function correctly creates a tree with a single node.
Duplicate Values: The problem statement specifies that the input arrays consist of unique values. If there were duplicate values, the inorder.index() call would return the first occurrence, potentially leading to an incorrect tree structure. Handling duplicate values would require a more sophisticated approach, such as tracking the ranges of valid indices for each subtree.
Invalid Input: If the input arrays do not represent valid preorder and inorder traversals of the same tree (e.g., they have different lengths or contain different values), the algorithm might produce an incorrect tree or raise an exception. Input validation could be added to check for these cases.