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 the element is found in inorder, the left and right subtrees can be determined based on the elements to the left and right of the element in the inorder array. This approach would be highly inefficient due to the repeated searching in the inorder array.

Optimal Approach

The optimal approach uses a recursive algorithm combined with a hash map to store the indices of the inorder array elements. This allows for quick lookups during the tree construction. Here's a breakdown:

1. Build a Hash Map: Store the indices of each element in the inorder array in a hash map for O(1) access.
2. Recursive Function:
   • The first element in preorder is always the root of the current subtree.
   • Find the index of this root in the inorder array using the hash map.
   • The elements to the left of the root in inorder form the left subtree, and the elements to the right form the right subtree.
   • Recursively construct the left and right subtrees using the corresponding portions of the preorder and inorder arrays.

Code Implementation (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_map = {val: i for i, 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_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)

Example

preorder = [3, 9, 20, 15, 7]
inorder = [9, 3, 15, 20, 7]
root = buildTree(preorder, inorder)
# The 'root' variable now holds the constructed binary tree.

Edge Cases

• Empty Arrays: If either preorder or inorder is empty, return None.
• Single Node: If both arrays contain only one element, create a single node tree.
• Invalid Input: If preorder and inorder do not represent the same tree (e.g., different lengths or inconsistent values), the algorithm may produce an incorrect tree or enter an infinite loop (though the problem statement guarantees valid input).

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. This is because we visit each node once during the tree construction.
• Space Complexity: O(N) in the worst case due to the hash map storing the inorder indices and the recursion stack. In the case of a skewed tree, the recursion stack can grow to a depth of N.