106 · Construct Binary Tree from Inorder and Postorder

Postorder is consumed from the right, and therefore the right subtree is built before the left. Write this immediately after LC 105 or the two will fuse in memory — they differ in exactly one line, and it is not the line you expect.

1 — The problem

Same job as LC 105, different pair of traversals. Postorder plays the role preorder played, but mirrored:

The last row is the one that catches people, and it is not arbitrary. With a shared cursor walking backwards, the values arrive in reverse postorder: root, then everything in the right subtree, then everything in the left. The recursion must consume them in that order, so the right call has to come first.

Get this wrong and the code still runs, still terminates, and produces a tree that is wrong in a structured, almost-plausible way — subtrees attached to the wrong sides. There is no exception to catch it.

2 — Consuming postorder backwards

Watch the post cursor: it starts at the far right and only ever moves left, and the order in which nodes light up in the tree is root → right subtree → left subtree.

Node 9 — the first element of postorder — is the last one consumed. That inversion is the whole character of this problem.

2.1 Why the shared cursor forces the order

Reverse the postorder array and read it left to right: 3, 20, 7, 15, 9. That sequence is exactly root, right subtree, left subtree, applied recursively — a mirrored preorder. The cursor hands out values in that sequence and cannot be asked for them in any other, because it is one shared variable, not a range.

So the build order is not a stylistic choice; it is dictated by the data structure you chose to track position with. The four-index version below has no such constraint — each call gets explicit bounds — and there the order genuinely does not matter:

private TreeNode build(int inL, int inR, int poL, int poR) {
    if (inL > inR) return null;
    int v = postorder[poR];              // root is LAST in postorder
    int k = idx.get(v);
    int leftSize = k - inL;
    TreeNode nd = new TreeNode(v);
    nd.left  = build(inL, k - 1, poL, poL + leftSize - 1);
    nd.right = build(k + 1, inR, poL + leftSize, poR - 1);
    return nd;
}

Note poL + leftSize - 1 here, where LC 105 had preL + leftSize with no -1. The difference is that 105's range began with the root, absorbing the off-by-one; postorder's range does not. Two problems, two different-looking bounds, both derived from the same three-piece decomposition — which is the argument for deriving them each time rather than remembering them.

2.2 Which pairs of traversals actually work

3 — Complexity and edge cases

• Time O(n) with the index map, space O(n) for the map plus O(h) for the recursion.
• Empty input: the first call has inL > inR and returns null.
• Single node: consumed on the first read; both children hit the guard.
• Duplicate values: unanswerable, same as LC 105.
• Common bug: building left before right with the shared cursor. Silent, structured wrongness.
• Common bug: initialising the cursor to postorder.length instead of length - 1, or using --post instead of post--. Both are immediate out-of-bounds, which is the friendly failure.
• Common bug: making the cursor a local parameter instead of shared state. Each frame then starts from its own copy and the same value is consumed repeatedly.

4 — Reference implementation

private int[] postorder;
private int post;
private Map<Integer, Integer> idx = new HashMap<>();

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

private TreeNode build(int inL, int inR) {
    if (inL > inR) return null;
    int v = postorder[post--];        // root is the last unconsumed value
    TreeNode nd = new TreeNode(v);
    int k = idx.get(v);
    nd.right = build(k + 1, inR);       // RIGHT first — the cursor demands it
    nd.left  = build(inL, k - 1);
    return nd;
}