Construct Binary Tree from Inorder and Postorder Traversal

The root is easy to identify. The difficult part is preserving the remaining traversal state while the tree splits into subtrees.

The reliable model is:

• Postorder reveals the current root from the end.
• Inorder reveals the left/right boundary around that root.
• Because postorder is consumed backward, build the right subtree before the left subtree.

That combination produces an O(n) Construct Binary Tree from Inorder and Postorder Traversal solution.

The contract and the key observation

You receive two traversals of the same binary tree:

• inorder: left subtree, root, right subtree
• postorder: left subtree, right subtree, root

The values are unique, both arrays have the same length, and every value in postorder appears in inorder.

Consider:

inorder   = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]

The last postorder value is 3, so 3 must be the root.

In the inorder array:

[9, 3, 15, 20, 7]
    ^

Everything to the left of 3 belongs to the left subtree. Everything to the right belongs to the right subtree:

left subtree       root       right subtree
[9]                 3         [15, 20, 7]

This gives us two separate jobs:

1. Use postorder to choose the next root.
2. Use inorder to divide the current subtree into two ranges.

The implementation becomes fast when we index the inorder positions once:

inorder_index = {
    9: 0,
    3: 1,
    15: 2,
    20: 3,
    7: 4,
}

Then locating a root in inorder takes O(1) time instead of scanning.

Start with the brute-force reconstruction

For a current subtree, the straightforward recursive approach is:

1. Take the last value in its postorder range as the root.
2. Scan the corresponding inorder range to find that root.
3. Recursively construct the left and right subtrees.

This is useful as a baseline because it exposes the real bottleneck: repeated root searches.

For a completely skewed tree, the first search may inspect almost the entire inorder array, the next search almost the entire remaining range, and so on:

n + (n - 1) + (n - 2) + ... + 1 = O(n²)

Array slicing can also create unnecessary work. If every recursive call copies pieces of inorder and postorder, those copies add time and memory overhead.

The optimized version keeps the original arrays intact and passes only inclusive index boundaries. That makes every recursive call describe a range rather than allocate a new array.

Define the recursive state and invariant

Let:

dfs(in_left, in_right)

build the subtree whose inorder values occupy the inclusive range:

inorder[in_left : in_right + 1]

The key invariant is:

dfs(in_left, in_right) returns exactly the subtree containing the values in that inorder interval, while the shared postorder cursor points to the next root that must be consumed for this subtree.

The recursive state needs:

• in_left: first index of the current inorder range
• in_right: last index of the current inorder range
• post_index: the last unconsumed position in postorder
• inorder_index: a map from node value to its inorder position

The base case is direct:

if in_left > in_right:
    return None

An empty inorder range represents an empty subtree.

Why the right subtree comes first

Postorder visits nodes in this order:

left subtree → right subtree → root

If we consume postorder from the end, the order reverses:

root → right subtree → left subtree

After consuming the current root, the next unconsumed value belongs to the right subtree, not the left.

This is the failure point in many plausible implementations. The root is correct, the inorder split is correct, but building the left child first consumes a right-subtree value and attaches the wrong structure.

The recursion must therefore be:

build root
build right subtree
build left subtree

Derive the optimized algorithm step by step

For each recursive call:

1. Stop if the inorder range is empty.
2. Read postorder[post_index] as the current root.
3. Move post_index backward.
4. Find the root's position in inorder using the hash map.
5. Build the right range.
6. Build the left range.
7. Attach both children to the root.

If the root is at root_index in inorder, the ranges are:

left:  [in_left, root_index - 1]
right: [root_index + 1, in_right]

The distance from in_left to root_index also gives the left subtree size:

left_size = root_index - in_left

You do not need that size when using a shared backward cursor and inorder boundaries, but calculating it is a useful way to verify the split.

Dry run

Use:

inorder   = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]

Start with:

inorder range = [0, 4]
post_index    = 4

Step	Consumed value	Inorder range	Root position	Next recursive range
1	3	[0, 4]	1	Build right [2, 4]
2	20	[2, 4]	3	Build right [4, 4]
3	7	[4, 4]	4	Empty right, then empty left
4	15	[2, 2]	2	Empty right, then empty left
5	9	[0, 0]	0	Empty right, then empty left

The resulting tree is:

        3
       / \
      9   20
         /  \
        15   7

Notice the consumption order:

3 → 20 → 7 → 15 → 9

That is the reverse of the original postorder traversal:

9 → 15 → 7 → 20 → 3

The recursion follows that reversed order structurally: root, right, left.

Why the construction is correct

We can prove correctness using the recursive invariant.

Assume dfs(in_left, in_right) is called for a valid inorder interval.

Base case

If:

in_left > in_right

the interval contains no values. Returning None correctly represents an empty subtree.

Root selection

For a non-empty interval, the next unconsumed postorder value is the root of this subtree. That follows directly from the postorder rule: the root appears after both child subtrees.

Because we consume from the end, the shared cursor must point to that root.

Inorder partition

The root has a unique position in inorder. Values before that position belong to the left subtree, and values after it belong to the right subtree.

Therefore:

[in_left, root_index - 1]

contains exactly the left subtree values, and:

[root_index + 1, in_right]

contains exactly the right subtree values.

The two ranges are disjoint and together contain every non-root value in the current subtree.

Consumption order

After consuming the root, the backward postorder cursor points to the right subtree's root. Building the right subtree first consumes all of its values. The cursor then reaches the left subtree's root, so the left subtree can be built next.

Each node is consumed exactly once. By induction, both recursive calls construct the correct subtrees, and attaching them to the selected root constructs the correct current subtree.

The uniqueness assumption matters here. With unique values, the inorder map gives one unambiguous position for each root. Duplicate values would require additional state because a value alone would not identify a unique inorder position.

Python implementation

The following implementation uses the standard TreeNode type supplied by the coding platform.

class Solution:
    def buildTree(self, inorder, postorder):
        if not inorder or not postorder:
            return None

        inorder_index = {
            value: index
            for index, value in enumerate(inorder)
        }

        post_index = len(postorder) - 1

        def dfs(in_left, in_right):
            nonlocal post_index

            # No values in this inorder interval means no subtree.
            if in_left > in_right:
                return None

            # The last unconsumed postorder value is this subtree's root.
            root_value = postorder[post_index]
            post_index -= 1

            root_index = inorder_index[root_value]
            root = TreeNode(root_value)

            # Postorder is being consumed backward:
            # root, right subtree, left subtree.
            root.right = dfs(root_index + 1, in_right)
            root.left = dfs(in_left, root_index - 1)

            return root

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

The variables have specific obligations:

• inorder_index removes repeated linear searches.
• post_index tracks the next root to consume.
• in_left and in_right define the exact subtree being built.
• The right-first recursion preserves the reversed postorder consumption order.

I prefer this version over one based on array slicing in an interview because the state is visible. You can point to the interval invariant, point to the cursor, and explain every recursive call without hiding work inside copied arrays.

Common implementation mistakes

Building the left subtree first

This is the most important error.

A backward postorder cursor sees:

root → right → left

So this is wrong:

root.left = dfs(...)
root.right = dfs(...)

The first recursive call consumes a value from the right subtree but attaches it as the left child.

Mixing inclusive and exclusive boundaries

The implementation above uses inclusive ranges:

[in_left, in_right]

That means the empty condition is:

in_left > in_right

If you switch to half-open ranges such as [in_left, in_right), the base case and child boundaries must change as well. Both conventions work. Mixing them produces off-by-one errors that often appear only on leaves or skewed trees.

Decrementing the cursor at the wrong time

The cursor should move immediately after reading the current root:

root_value = postorder[post_index]
post_index -= 1

If it moves after recursive calls, or moves more than once per node, the recursion loses alignment with postorder.

Searching the entire inorder array

The root must be located within the current subtree's range conceptually. With valid unique-value input, a global value-to-index map is safe because each value appears once. Scanning the array at every call throws away the reason for using indexed lookup.

Ignoring the empty-input case in reusable code

The stated problem constraints require at least one node, but a reusable tree builder should still handle:

inorder = []
postorder = []

Returning None makes the helper safe without complicating the main algorithm.

Complexity, edge cases, and interview checks

Let n be the number of nodes.

Time complexity

Building the inorder map takes O(n).

Each node is:

• read once from postorder
• turned into one TreeNode
• looked up once in the map
• processed by a constant amount of pointer and boundary logic

Therefore the total time is:

O(n)

Space complexity

The inorder map stores n entries, and the recursion stack can contain up to n calls for a completely skewed tree.

So auxiliary space is:

O(n)

The returned tree itself also contains n nodes. If the output structure is counted separately, the additional working space is still O(n) because of the map and recursion stack.

Edge cases to test

One node

inorder   = [5]
postorder = [5]

The root is 5; both child ranges are empty.

Completely left-skewed tree

inorder   = [4, 3, 2, 1]
postorder = [4, 3, 2, 1]

Every node has an empty right range. The algorithm must still consume values in reverse:

1 → 2 → 3 → 4

Completely right-skewed tree

inorder   = [1, 2, 3, 4]
postorder = [4, 3, 2, 1]

Every node has an empty left range. This case exposes incorrect cursor movement quickly.

Validation

A strong debugging check is to traverse the constructed tree again:

• its inorder traversal should equal the supplied inorder
• its postorder traversal should equal the supplied postorder

If either traversal differs, inspect the cursor movement and the order of the recursive calls before changing anything else.

Although this problem appears under a Two Pointers category, it is not a conventional opposite-ends array problem. The useful lens is coordinated index movement: one index narrows an inorder range, while another moves backward through postorder. The underlying algorithm is divide-and-conquer supported by hashing.

The transferable recognition rule

When one traversal identifies the current subtree root and another places that root between two contiguous regions, use the root's position to split the problem into ranges.

Then ask one final question:

In what direction am I consuming the root-revealing traversal?

Here, postorder reveals roots from the end, so the valid construction order is:

root → right → left

Preserve that order, keep the subtree interval invariant explicit, and the implementation becomes mechanical rather than memorable magic. A useful next comparison is the preorder-plus-inorder variant: preorder reveals roots from the front, so the child-construction order changes.