Construct Binary Tree from Inorder and Postorder Traversal

May 13, 20267 min read

leetcodeproblemmediumtrees

You are given two integer arrays, inorder and postorder, representing the inorder and postorder traversals of the same binary tree. Your job is to reconstruct the original tree and return its root.

This is LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal. If you have already solved the preorder + inorder version (LeetCode 105), you will find this problem nearly identical. The only difference is where you pull the root from.

Example: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3] produces the tree [3, 9, 20, null, null, 15, 7].

The last element of postorder is always the root. Find it in inorder to split left and right subtrees.

The key insight

Postorder traversal visits nodes in the order: left subtree, right subtree, root. That means the last element of postorder is always the root of the current tree. Compare that to preorder, where the first element is the root. Once you have the root, the rest of the algorithm is the same:

Take the last element of postorder. That is the root.
Find that value in inorder. Everything to its left belongs to the left subtree. Everything to its right belongs to the right subtree.
Use the count of left-subtree nodes to figure out where the left and right halves sit inside postorder.
Recurse on both halves.

If you solved the preorder + inorder version by iterating forward through preorder, you solve this one by iterating backward through postorder. And because postorder ends with the root and the right subtree comes just before the root, you must build the right subtree before the left when consuming values from the end.

Step-by-step walkthrough

Using inorder = [9, 3, 15, 20, 7] and postorder = [9, 15, 7, 20, 3], the target tree is:

Step 1: postorder[-1] = 3 is the root. Find 3 in inorder at index 1.

Everything left of 3 in inorder is the left subtree. Everything right is the right subtree.

Step 2: Right subtree first. postorder gives 20 as right subtree root.

Build right subtree before left (reverse of postorder). Find 20 in inorder at index 3.

Step 3: 7 becomes 20's right child, 15 becomes 20's left child.

Single-element partitions become leaves. Right subtree of 3 is complete.

Step 4: Left subtree has 1 element. 9 becomes 3's left child. Done!

Only [9] in the left partition. Single element becomes a leaf. The tree is fully reconstructed.

Each recursive call does the same thing: grab the root from the end of the current postorder range, find it in inorder, split, and recurse. The recursion bottoms out when a partition is empty, meaning there is no subtree on that side.

Practice tree construction with spaced repetition

The code

Here is the implementation using a reverse iterator over postorder. The hash map gives O(1) lookups for the root index in inorder.

def build_tree(inorder, postorder):
    inorder_index = {val: i for i, val in enumerate(inorder)}
    post_iter = reversed(postorder)

    def build(in_start, in_end):
        if in_start > in_end:
            return None

        root_val = next(post_iter)
        root = TreeNode(root_val)

        mid = inorder_index[root_val]

        root.right = build(mid + 1, in_end)
        root.left = build(in_start, mid - 1)

        return root

    return build(0, len(inorder) - 1)

Let's break down why this works:

The reversed iterator trick. Postorder visits left, right, root. When you reverse it, you get root, right, left. So calling next(post_iter) gives you the root first, then the right subtree values, then the left subtree values. This is exactly the order you need if you build right before left.

Right before left. This is the critical difference from the preorder + inorder version. In that version, you build left before right because preorder visits left first. Here, the reversed postorder visits right first, so you must call build for the right subtree before the left subtree. Swap the order and next(post_iter) will hand you the wrong value.

The hash map. Without it, finding the root in inorder takes O(n) per call, giving O(n^2) total. The hash map makes each lookup O(1).

The in_start and in_end bounds. These define which slice of inorder the current subtree corresponds to. When in_start > in_end, the slice is empty, meaning no subtree exists on that side.

The order of the two recursive calls matters. Because you are consuming postorder in reverse (root, right, left), you must build the right subtree first. If you build left first, the iterator will hand the right subtree's values to the left subtree's construction, and the tree will be wrong.

Dry run

Let's trace every recursive call to make sure the logic holds.

Call: build(0, 4) with reversed postorder [3, 20, 7, 15, 9]

next(post_iter) gives 3. Root is 3.
inorder_index[3] is 1. So mid = 1.
Right subtree: build(2, 4) (indices 2 through 4: values 15, 20, 7).
Left subtree: build(0, 0) (only index 0, which is value 9).

Call: build(2, 4) (right subtree of 3)

next(post_iter) gives 20. Root is 20.
inorder_index[20] is 3. So mid = 3.
Right: build(4, 4) (only index 4, value 7).
Left: build(2, 2) (only index 2, value 15).

Call: build(4, 4) (right subtree of 20)

next(post_iter) gives 7. Leaf node.

Call: build(2, 2) (left subtree of 20)

next(post_iter) gives 15. Leaf node.

Call: build(0, 0) (left subtree of 3)

next(post_iter) gives 9. Leaf node.

Every value consumed, every node placed. The tree is fully reconstructed.

Drill tree traversal patterns with CodeBricks

Complexity analysis

Metric	Value
Time	O(n)
Space	O(n)

Time is O(n). You visit each node exactly once. The hash map gives O(1) lookups, and the reversed iterator gives O(1) access to the next postorder value. No slicing, no searching.

Space is O(n). The hash map stores n entries. The recursion stack goes as deep as the tree height, which is O(n) in the worst case (a completely skewed tree) and O(log n) for a balanced tree. The hash map dominates.

The building blocks

This problem is built on two fundamental building blocks:

Root identification from traversal order. Postorder's last element is the root of the current subtree. Preorder's first element is the root. This property comes directly from the definitions of these traversals and is the key that unlocks any "construct tree from traversals" problem.

Recursive tree construction with index splitting. Once you know the root, you find it in inorder to determine the boundary between left and right subtrees. You then recurse on each side with adjusted index bounds. This same split-and-recurse pattern appears in the preorder + inorder version and in other divide-and-conquer tree problems.

# The skeleton for constructing from inorder + postorder:
def build(in_start, in_end):
    if in_start > in_end:
        return None
    root_val = next(post_iter)           # root from reversed postorder
    mid = inorder_index[root_val]        # find split point in inorder
    node = TreeNode(root_val)
    node.right = build(mid + 1, in_end)  # right partition first
    node.left = build(in_start, mid - 1) # then left partition
    return node

The ideas that transfer to other tree problems:

Postorder's last element is always the root of the current subtree. This is true by definition of postorder traversal (left, right, root).
Inorder splits left from right. Once you find the root in inorder, the partition is immediate.
A hash map eliminates repeated linear scans. This optimization pattern shows up in many problems where you need to find an element's position repeatedly.
An iterator avoids array slicing. Instead of creating new sub-arrays (O(n) per call), you advance a pointer through the original array.

Edge cases to watch for

Single node: both arrays have one element. The root is created, both recursive calls return None, and you get a single-node tree.
Left-only tree: postorder is [3, 2, 1] and inorder is [3, 2, 1]. Every node only has a left child. The right subtree is always empty.
Right-only tree: postorder is [3, 2, 1] and inorder is [1, 2, 3]. Every node only has a right child. The left subtree is always empty.
Duplicate values: the problem guarantees no duplicates. If duplicates existed, you could not uniquely identify the root's position in inorder. The hash map would also break because it maps each value to a single index.

From understanding to recall

You just traced through every recursive call and saw exactly how postorder (reversed) gives you roots and inorder gives you boundaries. The algorithm is the mirror image of the preorder + inorder version. But will you remember the differences in two weeks?

The tricky part is remembering that right must be built before left. It is easy to default to building left first since that is how preorder works. You also need to remember reversed(postorder) instead of iter(preorder), and that the recursive call order flips.

These details are easy to forget and hard to re-derive under pressure. Spaced repetition fixes that. You type the solution from scratch at increasing intervals. After a few reps, the distinction between preorder-first-left and postorder-last-right becomes automatic.

If you have already drilled the preorder + inorder version, this problem becomes a quick adaptation rather than a new problem from scratch. That is the power of identifying shared building blocks.

Construct Binary Tree from Preorder and Inorder - The sibling problem using preorder instead of postorder, sharing the same split-and-recurse pattern
Serialize and Deserialize Binary Tree - Another approach to encoding and decoding tree structure, useful for understanding what information is needed to uniquely reconstruct a tree

Try CodeBricks free