Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder — the inorder and postorder traversals of the same binary tree, where all values are unique — construct and return the binary tree.

The tree is returned in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

The last postorder value is the root of the (sub)tree.

Find the root in inorder to split into left and right subtrees.

Consume postorder from the back and build the right subtree before the left.

Common doubts

Reading postorder back-to-front, the elements right before the root belong to the right subtree (postorder is left, right, node).

Root is postorder's last (not preorder's first), and you recurse right-before-left instead of left-before-right.

So the root maps to a single inorder position and the split is unambiguous.

Interview follow-ups

· What an interviewer asks next.

Root is preorder's first; consume preorder front-to-back, left subtree before right.

Only up to ambiguity for single-child nodes — not a unique tree in general.

Fun facts

Preorder+inorder and inorder+postorder are mirror algorithms: front vs back pointer, left-first vs right-first.
Reversed postorder is exactly 'node, right, left' — a mirrored preorder — which is why the pointer runs backward.

Asked at

AmazonMicrosoftBloomberg

Frequently Sometimes Occasionally

Example 1

Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: [3, 9, 20, null, null, 15, 7]
Root 3 (postorder's last); right subtree rooted at 20, left subtree {9}.

Example 2

Input: inorder = [-1], postorder = [-1]
Output: [-1]
A single node.

Constraints

- 1 <= inorder.length <= 3000 - postorder.length == inorder.length - -3000 <= values <= 3000 - All values are unique - inorder and postorder are traversals of the same tree

This is the mirror of the preorder+inorder construction: postorder ends with the root (postorder[-1]), and inorder splits around it. The one twist — because you consume postorder from the back, you must build the right subtree before the left, since postorder is left, right, node.

Prerequisites

Before you start

· Concepts used directly in the solution.

Postorder & inorder. Postorder = left,right,node; inorder = left,node,right.

Root + split. Postorder's last element is the root; inorder gives the split.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Inputs

“Where is the root?”

The last element of postorder.

“Which subtree first?”

Right before left, because you read postorder backwards.

The ideal opening — say it like this

Postorder's last value is the root; I find it in inorder to split into left and right.

Reading postorder from the back, the value just before the root belongs to the right subtree, so I build right first, then left.

Understand the problem

Worked example — inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]

root = 3 (postorder last); in inorder, 3 at index 1
  right inorder = [15,20,7] -> root 20 -> 15 | 7
  left  inorder = [9]
result:
        3
       / \
      9   20
         /  \
        15   7

Key observations

1Aha

Root is postorder's last

Postorder puts the node after both subtrees, so the final element is the whole tree's root.

2Aha

Build right before left

Consuming postorder from the back yields the right subtree's root before the left's.

3Aha

Same map trick

A value→inorder-index map removes the per-node search — O(n).

Brute force vs optimal

	Slice + search inorder	Hash map + back pointer
Idea	Find root (postorder last) in inorder, slice	O(1) split; consume postorder from the back, right first
Time	O(n^2)	O(n)
Space	O(n^2)	O(n)

Both build the same tree. Full code is in the Approaches selector below.

Summary

Key takeaway

Root = postorder[-1]; split inorder around it; consume postorder from the back and build right before left. Value→index map for O(n).

build(lo, hi):
    if lo > hi: return null
    root = postorder[post--]; m = index[root]
    node.right = build(m+1, hi)
    node.left  = build(lo, m-1)