Construct Binary Tree from Inorder and Postorder Traversal

1. The main function buildTree initializes the process by calling a recursive helper function with the full range of both inorder and postorder arrays.
2. The recursive helper function buildHelper(inorder, inStart, inEnd, postorder, postStart, postEnd) works on the subarrays defined by the start and end indices.
3. Base Case: If the start index is greater than the end index for either array, it means the subarray is empty, and we return null.
4. Identify Root: The root of the current subtree is always the last element of the current postorder subarray (postorder[postEnd]). A new TreeNode is created with this value.
5. Find Root in Inorder: A linear search is performed on the current inorder subarray (from inStart to inEnd) to find the index of the root's value. Let's call this rootIndex.
6. Partition Subtrees:
   • The elements to the left of rootIndex in the inorder array (inStart to rootIndex - 1) belong to the left subtree.
   • The elements to the right of rootIndex (rootIndex + 1 to inEnd) belong to the right subtree.
7. Calculate Left Subtree Size: The number of nodes in the left subtree is calculated as leftSubtreeSize = rootIndex - inStart.
8. Recursive Calls:
   • The left child is constructed by a recursive call with the corresponding inorder and postorder subarrays for the left subtree.
   • The right child is constructed similarly with the subarrays for the right subtree.
9. Return Node: The constructed node with its left and right children attached is returned.

The algorithm is implemented using a recursive helper function that takes the start and end indices for the current segments of the inorder and postorder arrays. In each call, we first identify the root from the end of the postorder segment. Then, we iterate through the inorder segment to locate this root. This location tells us the boundary between the left and right subtrees. We can also determine the size of the left subtree, which helps in partitioning the postorder array for the subsequent recursive calls. The function then recursively calls itself to build the left and right children and connects them to the root.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode buildTree(int[] inorder, int[] postorder) {18        if (inorder == null || postorder == null || inorder.length == 0) {19            return null;20        }21        return buildHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);22    }23 24    private TreeNode buildHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {25        // Base case: if the subarray is empty26        if (inStart > inEnd || postStart > postEnd) {27            return null;28        }29 30        // The last element in the current postorder segment is the root31        int rootVal = postorder[postEnd];32        TreeNode root = new TreeNode(rootVal);33 34        // Find the root's index in the inorder array (Linear Search)35        int rootIndex = -1;36        for (int i = inStart; i <= inEnd; i++) {37            if (inorder[i] == rootVal) {38                rootIndex = i;39                break;40            }41        }42 43        // Calculate the size of the left subtree44        int leftSubtreeSize = rootIndex - inStart;45 46        // Recursively build the left subtree47        root.left = buildHelper(inorder, inStart, rootIndex - 1, 48                                postorder, postStart, postStart + leftSubtreeSize - 1);49        50        // Recursively build the right subtree51        root.right = buildHelper(inorder, rootIndex + 1, inEnd, 52                                 postorder, postStart + leftSubtreeSize, postEnd - 1);53 54        return root;55    }56}

1. Pre-computation: Create a HashMap to store the values of the inorder array as keys and their corresponding indices as values. This allows for O(1) lookup of a root's position in the inorder array.
2. Initialization: Initialize a global or class-level pointer, postIndex, to the last index of the postorder array (postorder.length - 1). This pointer will be used to traverse the postorder array from right to left.
3. Recursive Helper: Define a recursive helper function, buildHelper(inStart, inEnd), which takes the start and end indices of the current inorder segment.
4. Base Case: If inStart > inEnd, the current segment is empty, so return null.
5. Identify and Process Root:
   • The value of the current root is postorder[postIndex].
   • Create a new TreeNode with this value.
   • Decrement postIndex to move to the root of the next subtree in the postorder sequence.
6. Find Root in Inorder: Use the pre-computed HashMap to find the index of the root in the inorder array in O(1) time. Let this be rootIndex.
7. Recursive Calls (Crucial Order): Because we are processing postorder from right to left (which follows a Root -> Right Subtree -> Left Subtree pattern), we must build the right subtree before the left subtree.
   • Build Right Subtree: Make a recursive call buildHelper(rootIndex + 1, inEnd) and assign the result to root.right.
   • Build Left Subtree: After the right subtree is fully constructed, postIndex will correctly point to the root of the left subtree. Make a recursive call buildHelper(inStart, rootIndex - 1) and assign the result to root.left.
8. Return Root: Return the constructed root node.

The core of this optimized solution is a HashMap that maps each value in the inorder array to its index. This map is built once at the beginning. A global index, postIndex, is initialized to the end of the postorder array. The recursive function then does the following: it pops the last element from postorder (by using postorder[postIndex--]) to get the current root, creates the node, looks up its index in the inorder map to find the partition point, and then recursively builds the right and left subtrees. The key insight is the order of recursion: since the element before the root in a reversed postorder traversal is the root of the right subtree, the recursive call for the right child must be made before the call for the left child.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int postIndex;18    Map<Integer, Integer> inorderMap;19 20    public TreeNode buildTree(int[] inorder, int[] postorder) {21        if (inorder == null || postorder == null || inorder.length == 0) {22            return null;23        }24 25        // Start from the end of postorder, which is the root26        postIndex = postorder.length - 1;27        28        // Build a map for O(1) lookup of inorder indices29        inorderMap = new HashMap<>();30        for (int i = 0; i < inorder.length; i++) {31            inorderMap.put(inorder[i], i);32        }33 34        return buildHelper(0, inorder.length - 1);35    }36 37    private TreeNode buildHelper(int inStart, int inEnd) {38        // Base case: no elements to construct the tree39        if (inStart > inEnd) {40            return null;41        }42 43        // Get the current root value from postorder and move the index44        int rootVal = postorder[postIndex--];45        TreeNode root = new TreeNode(rootVal);46 47        // Get the index of the root from the inorder map48        int rootIndex = inorderMap.get(rootVal);49 50        // IMPORTANT: Build the right subtree first because we are traversing51        // postorder from right to left.52        root.right = buildHelper(rootIndex + 1, inEnd);53        54        // Then build the left subtree55        root.left = buildHelper(inStart, rootIndex - 1);56 57        return root;58    }59}