Construct Binary Tree from Preorder and Inorder Traversal

Problem Description

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.

Naive Approach

The naive approach would involve iterating through the preorder array and for each element, searching for it in the inorder array. Once found, we can determine the left and right subtrees based on the indices in the inorder array. This approach is inefficient because searching in the inorder array takes O(n) time for each element in the preorder array, leading to an overall time complexity of O(n^2).

Optimal Approach

The optimal approach utilizes a hash map to store the indices of the inorder array elements. This allows us to find the root node's index in O(1) time. We can then recursively build the left and right subtrees using the preorder and inorder arrays.

Algorithm:

1. Create a hash map to store the indices of the inorder array elements.
2. Implement a recursive function that takes the start and end indices of both the preorder and inorder arrays as input.
3. The first element in the preorder array represents the root of the current subtree. Create a new node with this value.
4. Find the index of the root node in the inorder array using the hash map.
5. Recursively build the left subtree using the appropriate indices in the preorder and inorder arrays.
6. Recursively build the right subtree using the appropriate indices in the preorder and inorder arrays.
7. Return the root node.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    inorder_index_map = {val: idx for idx, val in enumerate(inorder)}
    preorder_index = 0

    def build_subtree(inorder_start, inorder_end):
        nonlocal preorder_index
        if inorder_start > inorder_end:
            return None

        root_val = preorder[preorder_index]
        root = TreeNode(root_val)
        preorder_index += 1

        inorder_index = inorder_index_map[root_val]

        root.left = build_subtree(inorder_start, inorder_index - 1)
        root.right = build_subtree(inorder_index + 1, inorder_end)

        return root

    return build_subtree(0, len(inorder) - 1)

Big O Analysis

• Time Complexity: O(n), where n is the number of nodes in the tree. Building the hash map takes O(n) time, and the recursive function visits each node once.
• Space Complexity: O(n) in the worst case. The hash map stores n elements, and the recursion stack can grow up to a depth of n in a skewed tree.

Edge Cases

• Empty preorder or inorder arrays: Return None.
• Single node tree: The preorder and inorder arrays will both contain a single element. The algorithm should handle this case correctly.
• Duplicate values in the arrays: The problem statement specifies that the arrays consist of unique values, so this case does not need to be handled.

Example

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

root = buildTree(preorder, inorder)
# The tree will be constructed as expected.