Algorithm

Construct Tree from Inorder and Postorder

Trees Pattern

Construct Tree from Inorder and Postorder

You are given inorder, the values of a binary tree in the order an in-order traversal produces them, and postorder, the values in post-order. Rebuild the tree and return its root. All values are distinct, and the two arrays are guaranteed to come from the same tree, which they determine uniquely.

CONSTRAINTS
  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • All values in the tree are unique
  • inorder and postorder are guaranteed to be valid traversals of the same tree
EXAMPLE 1
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Post-order's last value is the root, 3. In-order then shows one value before it, so the left subtree holds only 9 and the other three belong on the right.
EXAMPLE 2
Input: inorder = [2,1], postorder = [2,1]
Output: [1,2]
The root is 1 (last in post-order), and 2 precedes it in-order, so 2 is the left child.
EXAMPLE 3
Input: inorder = [1,2], postorder = [2,1]
Output: [1,null,2]
Post-order is identical to the previous case, yet the tree differs — the in-order array alone decides which side 2 lands on.
EXAMPLE 4
Input: inorder = [1], postorder = [1]
Output: [1]
A single node is both the root and the whole tree, and the recursion's empty-range base case handles its two absent children.
How does this differ from the pre-order version?
Only in where the root sits: last in post-order instead of first in pre-order. That one change flips the order in which the two subtrees must be built.
Could I just reverse the post-order array and reuse the previous solution?
Nearly. Reversed post-order reads root, right, left — a mirrored pre-order — so the same code works if you also swap the roles of left and right. Many people find it cleaner to consume post-order from the back directly.
Are duplicate values allowed?
No, and the method depends on that: the root must be locatable in the in-order array by value, which requires exactly one occurrence.
Does the in-order array still carry the shape information?
Yes, exactly as before. Post-order names the roots; in-order says where each one splits its range.

Again two readings of one tree — this time in-order and post-order — and the job is to rebuild it.

Post-order walks left subtree → right subtree → node, so the root is the last value. In-order still does the splitting: wherever the root sits, everything before it is the left subtree, everything after is the right.

text
post: [ 9 15 7 20 | 3 ]      3 is the root (comes LAST)
                    ^root
in:   [ 9 | 3 | 15 20 7 ]     3 sits here -> LEFT = {9}, RIGHT = {15,20,7}
            ^root
Build the RIGHT subtree first

The tidy way to eat post-order: one index walking backwards from the end, taking one root per call. But look at what sits just before the root inside a segment:

text
segment:  [ ...left...  ...right...  root ]
                                ^ step back from root lands HERE = right subtree

Stepping back lands you in the right subtree, not the left. So the recursive calls must go right, then left — otherwise the backward index feeds right-subtree values into the left side.

python
pos = {v: i for i, v in enumerate(inorder)}   # value -> index in inorder
idx = len(postorder) - 1                       # walks backwards, one root per call

def build(lo, hi):                             # inclusive in-order range
    nonlocal idx
    if lo > hi:
        return None                            # empty range -> no subtree
    root = Node(postorder[idx])
    idx -= 1                                   # consume this root
    mid = pos[root.val]                        # where it splits the in-order range
    root.right = build(mid + 1, hi)            # RIGHT first — see the note
    root.left  = build(lo, mid - 1)
    return root

return build(0, len(inorder) - 1)
Crucial Notewith a single shared idx, the call order is what keeps everything aligned — there are no post-order boundaries being checked, so a mistake yields a plausible-looking (but silently mirrored) tree, not an error. Swap the two recursive lines and the right subtree's values become the left. The value-to-index map makes each split O(1); without it, scanning is O(N²). It relies on values being unique.
Watch it build

inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]. Follow idx from the back:

text
idx -> 3 : root 3,  in [9 | 3 | 15 20 7]  ->  left {9}, right {15,20,7}
idx -> 20: build RIGHT first. root 20, in [15 | 20 | 7] -> left {15}, right {7}
idx -> 7 :   right of 20 -> leaf 7
idx -> 15:   left  of 20 -> leaf 15
idx -> 9 : back to top, left of 3 -> leaf 9

result:        3
              / \
             9   20
                /  \
               15   7

The values idx visits — 3, 20, 7, 15, 9 — are post-order read backwards, which is root, right, left: exactly the order the recursion walks. O(N) time, O(N) space.

Interactive Strategy Visualization

Inorder + Postorder

Recursive Slicing Logic

Postorder Pick
9
15
7
20
3
Inorder Slicing
9
3
15
20
7
LEFT SUBTREE
ROOT
RIGHT SUBTREE
Subtree State
Starting construction. Look at last element of postorder.
CODE ANCHOR
rootNode = new Node(postorder[idx--]);
O(N²) Scan In-order For Each Root
→
O(N) Time · O(N) Space Hash Map With Backward Index