Construct Binary Tree from Inorder and Postorder Traversal

Share

Given inorder and postorder traversal arrays of the same binary tree, construct and return the 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=[2,1], postorder=[2,1] → Output: [1,2]

Solution Approach

The last element of postorder is the root. Find its position in inorder to split into left and right subtrees. Recurse right subtree first (because we consume postorder from end).

  • postIdx = postorder.length - 1.
  • Find root = postorder[postIdx--] in inorder using HashMap.
  • Build right subtree first (inorder[mid+1..hi]), then left (inorder[lo..mid-1]).
Java
import java.util.*;

class Solution {
    int postIdx;
    Map<Integer, Integer> inMap = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIdx = postorder.length - 1;
        for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
        return build(postorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] postorder, int lo, int hi) {
        if (lo > hi) return null;
        int rootVal = postorder[postIdx--];
        TreeNode root = new TreeNode(rootVal);
        int mid = inMap.get(rootVal);
        root.right = build(postorder, mid + 1, hi);
        root.left = build(postorder, lo, mid - 1);
        return root;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)