106. Construct Binary Tree from Inorder and Postorder Traversal

Problem Description

Given two integer arrays inorder and postorder representing the inorder and postorder traversals of a binary tree, respectively, construct and return the binary tree. The arrays contain unique values.

Solution: Hash Table + Recursion

This solution leverages the properties of inorder and postorder traversals to recursively build the tree.

Core Idea:

1. Root Identification: The last element in the postorder array is always the root of the tree.

2. Partitioning: Find the root's index in the inorder array. This index partitions the inorder array into left and right subtrees. The elements to the left of the root in inorder belong to the left subtree, and those to the right belong to the right subtree.

3. Recursive Construction: Recursively build the left and right subtrees using the corresponding portions of inorder and postorder. The lengths of these subarrays can be determined from the root's index in inorder.

4. Hash Table Optimization: A hash table (or dictionary) is used to efficiently find the root's index in the inorder array in O(1) time, avoiding repeated linear searches.

Algorithm:

1. Preprocessing: Create a hash table d mapping each value in inorder to its index.

2. Recursive Function dfs(i, j, n):

   • i: Starting index in inorder.
   • j: Starting index in postorder.
   • n: Number of nodes in the current subtree.
   • Base Case: If n <= 0, return null (empty subtree).
   • Root: The root is postorder[j + n - 1].
   • Partition: Find the index k of the root in inorder using d.
   • Recursive Calls: Recursively construct the left subtree (dfs(i, j, k - i)) and right subtree (dfs(k + 1, j + k - i, n - k + i - 1)).
   • Tree Construction: Create a new TreeNode with the root value and attach the left and right subtrees. Return the new node.

3. Initial Call: Call dfs(0, 0, len(inorder)) to build the entire tree.

Time and Space Complexity

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.

Space Complexity: O(N) due to the recursion stack and the hash table. In the worst case (a skewed tree), the recursion stack depth can be N. The hash table also stores N entries.

Code Examples

Python:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
class Solution:
    def buildTree(self, inorder, postorder):
        d = {val: i for i, val in enumerate(inorder)}  # Hash table
 
        def dfs(i, j, n):
            if n <= 0:
                return None
            root_val = postorder[j + n - 1]
            k = d[root_val]
            root = TreeNode(root_val)
            root.left = dfs(i, j, k - i)
            root.right = dfs(k + 1, j + k - i, n - k + i - 1)
            return root
 
        return dfs(0, 0, len(inorder))
 

Java: (Similar structure to Python; uses a HashMap)

import java.util.HashMap;
import java.util.Map;
 
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {this.val = val;}
}
 
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        Map<Integer, Integer> d = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            d.put(inorder[i], i);
        }
 
        return dfs(inorder, postorder, 0, 0, inorder.length);
    }
 
    private TreeNode dfs(int[] inorder, int[] postorder, int i, int j, int n){
        if(n <=0) return null;
        int root_val = postorder[j + n - 1];
        int k = d.get(root_val);
        TreeNode root = new TreeNode(root_val);
        root.left = dfs(inorder, postorder, i, j, k - i);
        root.right = dfs(inorder, postorder, k + 1, j + k -i, n - k + i - 1);
        return root;
    }
 
}

(Other languages like C++, Go, Javascript would follow a similar recursive approach with appropriate data structures.)

This detailed explanation and code examples should help you understand the solution to this problem effectively. Remember to adapt the code to your preferred programming language using the appropriate data structures (like HashMaps or dictionaries for the hash table).