Naive Approach: Brute Force (Inefficient)

For each element in preorder, we'd search for it in inorder. The index of this element in inorder would tell us how many elements are in the left subtree. We could then recursively build the tree. However, the constant searching in inorder makes this approach very inefficient.

Time Complexity: O(N^2) in the worst case, where N is the number of nodes. Space Complexity: O(N) for the recursion stack.

Optimal Approach: Using a HashMap

1. Core Idea: The key is to use the preorder array to determine the root node and the inorder array to determine the structure (left and right subtrees) of the tree. A HashMap to store the indices of the inorder array allows for O(1) lookup during tree construction.
2. Algorithm:
   • Create a HashMap that stores the index of each value in the inorder array.
   • Start with the first element of the preorder array, which is the root of the tree.
   • Find the index of this root value in the inorder array. This index divides the inorder array into left and right subtrees.
   • Recursively build the left subtree using the portion of the preorder and inorder arrays corresponding to the left subtree.
   • Recursively build the right subtree using the portion of the preorder and inorder arrays corresponding to the right subtree.
3. Edge Cases:
   • Empty preorder or inorder arrays: return null.
   • Single-node tree: return a tree node with the single value.

import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    int preorderIndex = 0;
    HashMap<Integer, Integer> inorderIndexMap;
    int[] preorder;
    int[] inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        return arrayToTree(0, preorder.length - 1);
    }

    private TreeNode arrayToTree(int left, int right) {
        if (left > right)
            return null;

        int rootValue = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootValue);

        root.left = arrayToTree(left, inorderIndexMap.get(rootValue) - 1);
        root.right = arrayToTree(inorderIndexMap.get(rootValue) + 1, right);

        return root;
    }
}

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once.

Space Complexity: O(N) in the worst case. This is due to the HashMap which stores all the inorder elements, and the recursion stack which can go as deep as N in a skewed tree. In a balanced tree, the recursion stack space is O(log N).