L35. Construct the Binary Tree from Postorder and Inorder Traversal

1. Why Do We Need This? (Problem Statement & Status Quo)

When working with Binary Trees, standard traversal techniques convert a hierarchical tree structure into linear sequences (arrays or lists). However, the inverse operation—reconstructing a binary tree from its traversal outputs—is a fundamental algorithmic challenge.

A crucial theoretical constraint governs this domain:

• Single traversals (like Preorder alone, Postorder alone, or Inorder alone) are insufficient to construct a unique binary tree. Multiple structurally distinct trees can produce the exact same Preorder or Inorder sequence.
• Combining Inorder with either Preorder or Postorder guarantees a unique binary tree.

This chapter focuses on the specific problem: Given an Inorder traversal array and a Postorder traversal array, reconstruct the original binary tree and return its root node.

2. Core Mental Model & Traversal Properties

To build an efficient reconstruction algorithm, we must analyze the structural contracts of Postorder and Inorder traversals:

• Inorder Traversal Sequence: Follows the pattern [Left Subtree] -> [Root] -> [Right Subtree]. This sequence tells us which elements reside to the left and right of any given root.
• Postorder Traversal Sequence: Follows the pattern [Left Subtree] -> [Right Subtree] -> [Root]. This sequence guarantees that the very last element of the array is always the Root of the current tree (or subtree).

Real-Life Analogy: The Dispatch and Assembly Line

Imagine receiving a disassembled mechanical clock. You are handed two instruction sheets:

1. The Inorder Sheet: Tells you the exact left-to-right spatial layout of all gears once mounted on the board.
2. The Postorder Sheet: Tells you the exact sequence in which the components were uninstalled, revealing that the main chassis (the root) is always unbolted and listed last in the teardown log.

By looking at the teardown log, you instantly identify the master chassis. You then look at the spatial layout sheet, find that chassis, and instantly separate all gears to its left into the "Left Subassembly Box" and all gears to its right into the "Right Subassembly Box".

3. Naive vs. Optimal Subproblem Breakdown

The Recursive Principle

The problem exhibits optimal substructure. Once the root is identified from the Postorder array:

1. Locate that root value inside the Inorder array.
2. Partition the Inorder array into a Left Inorder Segment and a Right Inorder Segment.
3. Partition the Postorder array correspondingly into Left Postorder Segment and Right Postorder Segment based on the count of elements in the left subtree.
4. Recursively build the left and right subtrees, attaching them to the root.

Naive Array Slicing vs. Pointer-Based Indexing

• Naive Approach: Actually slicing and copying sub-arrays in memory for every recursive call. This introduces $O(N^2)$ or $O(N \log N)$ time overhead and excessive memory allocation.
• Optimal Approach: Maintain integer boundary pointers (inStart, inEnd, postStart, postEnd) referencing the original arrays, avoiding any physical array copying.

4. Step-by-Step Flow Walkthrough

Consider building a tree from:

• Inorder: [40, 20, 50, 10, 60, 30]
• Postorder: [40, 50, 20, 60, 30, 10]

Step 1: Identify the Root

• Look at the last element of the Postorder array: 10.
• Root Node = 10.

Step 2: Partition via Inorder Map

• Locate 10 in the Inorder array. It sits at index 3.
• Elements to the left of index 3: [40, 20, 50] (Left Subtree Inorder).
• Elements to the right of index 3: [60, 30] (Right Subtree Inorder).

Step 3: Split Postorder Segments

• Count of elements in the left subtree = 3 (40, 20, 50).
• Left Postorder Segment takes the first 3 elements of Postorder: [40, 50, 20].
• Right Postorder Segment takes the remaining elements (excluding the root): [60, 30].

Step 4: Recursive Subtree Construction

• Recursively repeat the process for left and right segments until boundaries cross (start > end), returning nullptr (or null).

5. Hash Map Optimization for $O(1)$ Lookups

To avoid scanning the Inorder array linearly every time we need to find a root's index, we pre-populate a Hash Map:

• Key: Element value from the Inorder array.
• Value: Its corresponding index in the Inorder array.

This reduces the root-lookup operation from $O(N)$ to $O(1)$ average time complexity.

6. Complete Implementation Code (C++ & Java)

C++ Implementation

#include <vector>
#include <unordered_map>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    TreeNode* buildTreeHelper(const std::vector<int>& inorder, int inStart, int inEnd,
                              const std::vector<int>& postorder, int postStart, int postEnd,
                              std::unordered_map<int, int>& inMap) {
        if (inStart > inEnd || postStart > postEnd) return nullptr;

        // The last element in the current postorder range is the root
        TreeNode* root = new TreeNode(postorder[postEnd]);

        // Find the root index in the inorder array using the hash map in O(1)
        int inRoot = inMap[root->val];
        int numsLeft = inRoot - inStart;

        // Recursively build left and right subtrees
        root->left = buildTreeHelper(inorder, inStart, inRoot - 1,
                                     postorder, postStart, postStart + numsLeft - 1, inMap);
        
        root->right = buildTreeHelper(inorder, inRoot + 1, inEnd,
                                      postorder, postStart + numsLeft, postEnd - 1, inMap);

        return root;
    }

public:
    TreeNode* buildTree(std::vector<int>& inorder, std::vector<int>& postorder) {
        if (inorder.size() != postorder.size() || inorder.empty()) return nullptr;

        std::unordered_map<int, int> inMap;
        for (int i = 0; i < inorder.size(); ++i) {
            inMap[inorder[i]] = i;
        }

        return buildTreeHelper(inorder, 0, inorder.size() - 1,
                               postorder, 0, postorder.size() - 1, inMap);
    }
};

Java Implementation

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null || inorder.length != postorder.length) {
            return null;
        }

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

        return buildTreeHelper(inorder, 0, inorder.length - 1,
                               postorder, 0, postorder.length - 1, inMap);
    }

    private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd,
                                     int[] postorder, int postStart, int postEnd,
                                     Map<Integer, Integer> inMap) {
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd]);
        int inRoot = inMap.get(root.val);
        int numsLeft = inRoot - inStart;

        root.left = buildTreeHelper(inorder, inStart, inRoot - 1,
                                    postorder, postStart, postStart + numsLeft - 1, inMap);
        
        root.right = buildTreeHelper(inorder, inRoot + 1, inEnd,
                                     postorder, postStart + numsLeft, postEnd - 1, inMap);

        return root;
    }
}

7. Complexity Analysis

8. Summary and Key Takeaways

• Uniqueness Condition: A binary tree can be uniquely reconstructed if and only if Inorder is provided alongside either Preorder or Postorder.
• Postorder Root Contract: The last element of a Postorder traversal array is always the root of the current tree or subtree.
• Inorder Partitioning: Locating the root within the Inorder sequence cleanly divides the array into left and right subtree components.
• Index Pointer Arithmetic: Using start and end indices (inStart, inEnd, postStart, postEnd) avoids costly physical array slicing and memory reallocation.
• HashMap Acceleration: Pre-indexing Inorder element positions in a hash map guarantees $O(1)$ lookups, optimizing total execution time to linear $O(N)$.
• Recursive Backtracking: Subtrees are built bottom-up via recursion and attached to their respective parent nodes upon returning from base cases.