Construct Binary Tree from Inorder and Postorder Traversal Solution

Problem

Given the inorder and postorder traversal sequences of a binary tree, reconstruct and return the original tree. All node values are distinct, and the two traversals together fully determine the structure.

Example:

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

Input: inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]
Output: Root of the tree shown above
Explanation: 3 is the last element in postorder so it is the root; in inorder, [9] falls left of 3 and [15, 20, 7] falls right, giving 9 as the left child and 20 as the right child with children 15 and 7

Intuition

Postorder visits left → right → root, so the last element of postorder is always the overall root. Once you know the root, finding it in the inorder array draws a clean boundary: everything to its left belongs to the left subtree and everything to its right belongs to the right subtree. Repeating this logic recursively rebuilds the whole tree without ambiguity.

Approach 1 — Recursive with Slicing

Pull the root from postorder's last element, locate it in inorder to split the subtrees, then recurse on each slice.

Base case: return None if postorder is empty
The last element of postorder is the root
Find the root's position in inorder — left slice is the left subtree, right slice is the right subtree
The left subtree has mid elements, so take the first mid of postorder for the left recursion and the next segment (excluding the root at the end) for the right recursion
Recurse on both halves and return the root

1def buildTree(self, inorder, postorder):
2    if not postorder:
3        return None
4
5    root_val = postorder[-1]
6    root = TreeNode(root_val)
7
8    mid = inorder.index(root_val)  # O(n) linear scan per call
9
10    root.left = self.buildTree(inorder[:mid], postorder[:mid])
11    root.right = self.buildTree(inorder[mid + 1:], postorder[mid:-1])
12
13    return root

Time: O(n²) — the linear inorder scan plus array copies cost O(n) per node across n nodes.
Space: O(n²) — sliced arrays created at every recursion level total O(n²) for a skewed tree.

Approach 2 — Recursive with Index Map (Optimal)

Pre-build a hash map from value to inorder index, then walk postorder backwards with a shared pointer so no slicing or searching is needed.

Build a hash map from each value to its inorder index in O(n) up front
Set postIdx to the last index of postorder — this pointer always points to the current subtree's root
For each call: consume postorder[postIdx] as the root, decrement postIdx, then look up the root's inorder position in O(1)
Build the right subtree first, then the left — reading postorder backwards, right subtree elements appear before left subtree elements, so building right first keeps postIdx in sync
Return the constructed root

1def buildTree(self, inorder, postorder):
2    inorder_index = {val: idx for idx, val in enumerate(inorder)}
3    self.post_idx = len(postorder) - 1
4
5    def build(left, right):
6        if left > right:
7            return None
8
9        root_val = postorder[self.post_idx]
10        self.post_idx -= 1
11        root = TreeNode(root_val)
12
13        mid = inorder_index[root_val]  # O(1) lookup
14
15        root.right = build(mid + 1, right)  # right before left: reversed postorder visits right subtree first
16        root.left = build(left, mid - 1)
17
18        return root
19
20    return build(0, len(inorder) - 1)

Time: O(n) — each node is processed exactly once with O(1) hash map lookups.
Space: O(n) — the hash map holds n entries; the recursion stack is O(h), which is O(n) in the worst case for a skewed tree.

Complexity Summary

Approach	Time	Space	When to use
Recursive with slicing	O(n²)	O(n²)	Quick sketch or when input is small; easier to reason about the slices
Recursive with index map	O(n)	O(n)	Any real use; eliminates all linear scans and copying

Common Mistakes

Building the left subtree before the right in Approach 2 — reading postorder from back to front encounters right subtree roots before left subtree roots, so constructing right first keeps postIdx correctly synchronized
Calling .index() or a linear scan inside the recursion — this is exactly the bottleneck Approach 2 eliminates; doing it per call silently makes O(n) code into O(n²)
Confusing this with the preorder + inorder variant — that problem pulls the root from the first element of preorder; here the root is the last element of postorder, so the recursion order (right before left) is reversed
Slicing postorder with postorder[mid:] instead of postorder[mid:-1] — the root itself sits at the end and must be excluded from the right subtree's postorder slice
Applying this technique to trees with duplicate values — the hash map requires unique values to map correctly; the problem guarantees uniqueness, but the approach silently breaks if values repeat

Construct Binary Tree from Inorder and Postorder Traversal — Solution