Construct Binary Tree from Inorder and Postorder Traversal

Description

Construct Binary Tree from Inorder and Postorder Traversal

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.

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.
• inorder is guaranteed to be the inorder traversal of the tree.
• postorder is guaranteed to be the postorder traversal of the tree.

Approach 1: Recursive Divide & Conquer with HashMap ($O(N)$ Time, $O(N)$ Space)

Intuition

1. In postorder traversal ($\text{Left}\to \text{Right}\to \text{Root}$), the last element is always the root of the current tree/subtree.
2. Locating that root element in inorder splits the tree:
   • Everything to the left of the root index in inorder belongs to the left subtree.
   • Everything to the right belongs to the right subtree.
3. We store all inorder value-to-index mappings in a HashMap upfront for $O(1)$ lookups.
4. Key Difference from Preorder: Because we traverse postorder backwards from the end, we MUST build the right subtree before the left subtree.

import java.util.HashMap;
import java.util.Map;
 
class Solution {
    private int postIndex;
    private Map<Integer, Integer> inorderMap;
 
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        inorderMap = new HashMap<>();
 
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
 
        return build(postorder, 0, inorder.length - 1);
    }
 
    private TreeNode build(int[] postorder, int left, int right) {
        if (left > right) return null;
 
        // Pick root from postorder end
        int rootVal = postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);
 
        int inorderIndex = inorderMap.get(rootVal);
 
        // Crucial: Build RIGHT subtree first, then LEFT subtree
        root.right = build(postorder, inorderIndex + 1, right);
        root.left = build(postorder, left, inorderIndex - 1);
 
        return root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Pre-building inorderMap takes $O(N)$, and each node is processed once in $O(1)$ time.
• Space Complexity: $O(N)$ — $O(N)$ memory for the HashMap plus $O(H)$ recursion stack depth ($O(N)$ worst-case for skewed trees).

---

Approach 2: Iterative Stack ($O(N)$ Time, $O(N)$ Space)

Intuition

Iterate backwards through postorder from length - 1 down to 0 while maintaining an inorderIndex pointer starting from inorder.length - 1:

1. Push postorder[postorder.length - 1] as the root onto the stack.
2. Iterate backwards through postorder:
   • If stack top $\ne$ inorder[inorderIndex]: The current value is the right child of the stack top. Attach it to node.right and push it onto the stack.
   • If stack top $=$ inorder[inorderIndex]: We’ve reached the end of a right branch. Pop nodes from the stack while they match inorder[inorderIndex]. The current value is the left child of the last popped node. Attach it to node.left and push it onto the stack.

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
 
        int pLen = postorder.length;
        TreeNode root = new TreeNode(postorder[pLen - 1]);
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
 
        int inorderIndex = inorder.length - 1;
 
        for (int i = pLen - 2; i >= 0; i--) {
            int val = postorder[i];
            TreeNode node = stack.peek();
 
            if (node.val != inorder[inorderIndex]) {
                node.right = new TreeNode(val);
                stack.push(node.right);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex--;
                }
                node.left = new TreeNode(val);
                stack.push(node.left);
            }
        }
 
        return root;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each element in postorder is pushed and popped from the stack at most once.
• Space Complexity: $O(N)$ — Stack stores at most $N$ tree nodes.

---

Easy Memory Rule

“Last element of postorder is Root $\to$ Split inorder using HashMap $\to$ Build RIGHT subtree first because postorder processes backwards!”