Code Implementation

# Definition for a binary tree node.
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):
        if not inorder or not postorder:
            return None

        # Map value to index for quick lookup in inorder
        idx_map = {val: idx for idx, val in enumerate(inorder)}

        def helper(in_left, in_right):
            if in_left > in_right:
                return None

            # Last element in postorder is root
            root_val = postorder.pop()
            root = TreeNode(root_val)

            # Root splits inorder into left and right
            index = idx_map[root_val]

            # Build right subtree before left since we're popping from end
            root.right = helper(index + 1, in_right)
            root.left = helper(in_left, index - 1)

            return root

        return helper(0, len(inorder) - 1)
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        unordered_map idx_map;
        for (int i = 0; i < inorder.size(); ++i) {
            idx_map[inorder[i]] = i;
        }
        int post_idx = postorder.size() - 1;
        return helper(0, inorder.size() - 1, postorder, post_idx, idx_map);
    }

private:
    TreeNode* helper(int in_left, int in_right, vector& postorder, int& post_idx, unordered_map& idx_map) {
        if (in_left > in_right) return nullptr;
        int root_val = postorder[post_idx--];
        TreeNode* root = new TreeNode(root_val);
        int index = idx_map[root_val];
        root->right = helper(index + 1, in_right, postorder, post_idx, idx_map);
        root->left = helper(in_left, index - 1, postorder, post_idx, idx_map);
        return root;
    }
};
      

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private Map<Integer, Integer> idxMap;
    private int postIdx;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        idxMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            idxMap.put(inorder[i], i);
        }
        postIdx = postorder.length - 1;
        return helper(0, inorder.length - 1, postorder);
    }

    private TreeNode helper(int inLeft, int inRight, int[] postorder) {
        if (inLeft > inRight) return null;
        int rootVal = postorder[postIdx--];
        TreeNode root = new TreeNode(rootVal);
        int index = idxMap.get(rootVal);
        root.right = helper(index + 1, inRight, postorder);
        root.left = helper(inLeft, index - 1, postorder);
        return root;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    if (!inorder.length || !postorder.length) return null;

    const idxMap = new Map();
    inorder.forEach((val, idx) => idxMap.set(val, idx));

    function helper(inLeft, inRight) {
        if (inLeft > inRight) return null;
        const rootVal = postorder.pop();
        const root = new TreeNode(rootVal);
        const index = idxMap.get(rootVal);
        root.right = helper(index + 1, inRight);
        root.left = helper(inLeft, index - 1);
        return root;
    }

    return helper(0, inorder.length - 1);
};
      

Problem Description

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

• It is guaranteed that there is exactly one unique solution for the given traversal arrays.
• You must not reuse any tree node values; each value is unique and used once.
• Both arrays have the same length, and all elements are unique.

You need to reconstruct the original binary tree structure from these two traversals.

Thought Process

When first approaching this problem, you might try to brute-force all possible trees and compare their traversals to the given arrays. However, this would be extremely inefficient, especially as the number of nodes increases.

Instead, we should leverage the properties of inorder and postorder traversals:

• Inorder traversal (Left - Root - Right): The root node divides the tree into left and right subtrees.
• Postorder traversal (Left - Right - Root): The last element is always the root of the current tree/subtree.

By recursively identifying the root from postorder and splitting the inorder array accordingly, we can efficiently reconstruct the tree.

Solution Approach

We use recursion and a hash map for efficiency. Here are the steps:

1. Build a hash map mapping each value in inorder to its index. This allows O(1) lookups for splitting.
2. Start from the end of postorder (since the last element is the root).
3. Recursive function:
   • Pop the last value from postorder as the current root.
   • Find its index in inorder using the hash map.
   • Recursively build the right subtree first (because we are consuming postorder from the end).
   • Then recursively build the left subtree.
4. Base case: If the left index exceeds the right index in inorder, return null (no subtree).
5. Return the constructed root node.

We use a hash map for quick index lookups and avoid slicing arrays by passing indices, which keeps the solution efficient.

Example Walkthrough

Suppose inorder = [9,3,15,20,7] and postorder = [9,15,7,20,3].

1. The last element in postorder is 3. This is the root.
2. In inorder, 3 is at index 1. So:
   • Left subtree: inorder[0:1] = [9]
   • Right subtree: inorder[2:5] = [15,20,7]
3. Next, build the right subtree using postorder (remaining: [9,15,7,20]):
   • Root is 20 (last element).
   • In inorder, 20 is at index 3. So:
   • Left: [15]
   • Right: [7]
4. Recursively, right child of 20 is 7, and left child is 15. Both are leaf nodes.
5. Now, build the left subtree of 3 using postorder (remaining: [9]):
   • Root is 9, which is a leaf node.
6. The final tree structure is:
   • Root: 3
   • Left: 9
   • Right: 20
   • 20's left: 15
   • 20's right: 7

Time and Space Complexity

• Brute-force approach: Trying all possible trees would be exponential time and space, as the number of binary trees grows rapidly with n nodes.
• Optimized approach: Our solution visits each node exactly once, and each lookup in the hash map is O(1).
  • Time Complexity: O(n), where n is the number of nodes.
  • Space Complexity: O(n) for the hash map and recursion stack in the worst case (completely unbalanced tree).

Summary

By understanding the properties of inorder and postorder traversals, we can reconstruct a unique binary tree efficiently. The key insight is to use the last element of postorder as the root, use a hash map for fast splits, and build the right subtree first due to the traversal order. This approach is both elegant and efficient, making optimal use of recursion and data structures.