Construct Binary Tree from Postorder and Inorder Traversal

Problem Link

Construct Binary Tree from Inorder and Postorder Traversal – LeetCode

Problem: Construct Binary Tree from Inorder and Postorder Traversal

Problem Statement

Given two integer arrays inorder and postorder where:

• inorder is the inorder traversal of a binary tree.

• postorder is the postorder traversal of the same tree.

Construct and return the binary tree.

Examples

Example 1

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

Output:
    3
   / \
  9  20
     / \
    15  7

Example 2

Input:
inorder = [-1], 
postorder = [-1]

Output:
 -1

Constraints

• 1 <= inorder.length <= 3000

• postorder.length == inorder.length

• -3000 <= Node.val <= 3000

• All values in inorder and postorder are unique

• inorder and postorder represent a valid binary tree

Intuition

The last element of the postorder array is the root of the tree.
Using the inorder array, we can determine the elements belonging to the left and right subtrees of the root.

Approach

1. Create a map from inorder values to their indices for O(1) lookup.

2. Use a postIndex pointer (starting from the end of postorder) to keep track of the root.

3. Recursively:

   • Pick the current root from postorder[postIndex].

   • Find the index of root in inorder.

   • Recursively construct right subtree first, then left subtree, because we are moving backwards in postorder.

Code (Java)

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(inorder, postorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] inorder, int[] postorder, int inStart, int inEnd) {
        if (inStart > inEnd) return null;

        int rootVal = postorder[postIndex--];
        TreeNode root = new TreeNode(rootVal);

        int inIndex = inorderMap.get(rootVal);

        root.right = build(inorder, postorder, inIndex + 1, inEnd);
        root.left = build(inorder, postorder, inStart, inIndex - 1);

        return root;
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Each node is processed once. HashMap lookup is constant time.

• Space Complexity: O(N)
  HashMap stores N elements. Recursion stack can be O(N) in skewed trees.

Dry Run

Input:

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

• Start with postorder[4] = 3 → root

• In inorder, 3 is at index 1 → left = [9], right = [15,20,7]

• Next postorder element = 20 → build right subtree recursively

Conclusion

• This problem is a mirror of the preorder + inorder construction problem.

• Key trick is to process right subtree before left, since postorder ends with root → right → left (in reverse).

• Efficient hashmap indexing avoids repeated scanning of arrays.