The problem requires constructing a binary tree given two integer arrays, preorder and inorder, representing the tree's preorder and inorder traversals, respectively, and returning the root node.

The solution leverages the distinct properties of these traversal orders. In a preorder traversal, nodes are visited in the order: root, left subtree, right subtree. The first element is always the root. An inorder traversal visits nodes in the order: left subtree, root, right subtree. The root's position divides the inorder array into left and right subtrees.

Algorithm Overview

A recursive algorithm builds the tree by identifying the root from the preorder list and using its position in the inorder list to determine the sizes and elements of the left and right subtrees.

Optimization with a Hash Map

To efficiently find the root's index in the inorder array for each recursive call, a hash map stores a mapping from each node's value to its index in the inorder array. This reduces the lookup time from O(n) to O(1), making the overall time complexity O(n).

Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
    indexMap.put(inorder[i], i);
}

Recursive Construction Logic

Define a recursive function constructSubtree that takes index ranges for the current subtree in both arrays.

• Base Case: If the start index exceeds the end index for either array, the subtree is empty. Return null.
• Root Identification: The first element in the current preorder range (preorder[preStart]) is the root node's value.
• Subtree Division:
  • Find the root's position (rootPos) in the inorder array using the hash map.
  • The number of nodes in the left subtree is leftCount = rootPos - inStart.
• Recursive Calls:
  • Left Subtree: Construct using the next leftCount elements from the preorder list (starting after the root) and the left portion of the inorder list (before the root).
  • Right Subtree: Construct using the remaining elements from the preorder list and the right portion of the inorder list (after the root).
• Assembly: Create the root node, attach the recursively built left and right subtrees, and return it.

Index Boundary Calculations

Given a root at position rootPos in inorder:

• Left Subtree Inorder Range: [inStart, rootPos - 1]
• Right Subtree Inorder Range: [rootPos + 1, inEnd]
• Left Subtree Preorder Range: [preStart + 1, preStart + leftCount]
• Right Subtree Preorder Range: [preStart + leftCount + 1, preEnd]

Complexity Analysis

• Time Complexity: O(n). Each node is processed exactly once during the recursion, and the hash map enables O(1) root lookups.
• Space Complexity: O(n). The hash map uses O(n) space. The recursion call stack depth can be O(n) in the worst case of a skewed tree.

Implementation in Java

import java.util.HashMap;
import java.util.Map;

class TreeNode {
    int value;
    TreeNode leftChild;
    TreeNode rightChild;
    TreeNode() {}
    TreeNode(int val) { this.value = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.value = val;
        this.leftChild = left;
        this.rightChild = right;
    }
}

public class TreeBuilder {
    private Map<Integer, Integer> inorderIndexMap;

    public TreeNode buildFromTraversals(int[] preorder, int[] inorder) {
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        return constructSubtree(preorder, 0, preorder.length - 1,
                                inorder, 0, inorder.length - 1);
    }

    private TreeNode constructSubtree(int[] pre, int preL, int preR,
                                      int[] in, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }

        int rootValue = pre[preL];
        TreeNode rootNode = new TreeNode(rootValue);

        int inorderRootIndex = inorderIndexMap.get(rootValue);
        int nodesInLeftSubtree = inorderRootIndex - inL;

        rootNode.leftChild = constructSubtree(pre, preL + 1, preL + nodesInLeftSubtree,
                                              in, inL, inorderRootIndex - 1);

        rootNode.rightChild = constructSubtree(pre, preL + nodesInLeftSubtree + 1, preR,
                                               in, inorderRootIndex + 1, inR);

        return rootNode;
    }

    // Example usage
    public static void main(String[] args) {
        TreeBuilder builder = new TreeBuilder();
        int[] pre = {3, 9, 20, 15, 7};
        int[] in = {9, 3, 15, 20, 7};
        TreeNode root = builder.buildFromTraversals(pre, in);
    }
}

Step-by-Step Walkthrough

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

1. Initial Call: constructSubtree(pre, 0, 4, in, 0, 4)
   • Root value = pre[0] = 3. In inorder, index of 3 is 1.
   • Left subtree size = 1 - 0 = 1.
   • Create root node 3.
2. Build left subtree of 3: constructSubtree(pre, 1, 1, in, 0, 0)
   • Root value = pre[1] = 9. In inorder, index of 9 is 0.
   • Left subtree size = 0 - 0 = 0.
   • Create node 9. Its left and right child calls return null.
   • Attach node 9 as the left child of node 3.
3. Build right subtree of 3: constructSubtree(pre, 2, 4, in, 2, 4)
   • Root value = pre[2] = 20. In inorder, index of 20 is 3.
   • Left subtree size = 3 - 2 = 1.
   • Create node 20.
   • Recursively build its left child (15) and right child (7).
   • Attach the resulting subtree as the right child of node 3.