Construct Binary Tree from Inorder and Postorder Traversal
Last Updated: April 1, 2026
Understanding the Problem
We need to reconstruct a binary tree given its inorder and postorder traversals. To solve this, we need to understand what information each traversal gives us.
Inorder traversal visits nodes in the order: left subtree, root, right subtree. Postorder traversal visits nodes in the order: left subtree, right subtree, root. The critical observation is that the last element in the postorder array is always the root of the tree. Once we know the root, we can find it in the inorder array, and everything to its left in the inorder array belongs to the left subtree, while everything to its right belongs to the right subtree.
This gives us a natural recursive strategy: identify the root from postorder, split inorder around it, and recurse on both halves. The tricky part is figuring out which elements in the postorder array correspond to each subtree, and that's where the size of the left subtree (determined from inorder) becomes the key.
Key Constraints:
1 <= inorder.length <= 3000→ With n up to 3000, an O(n^2) approach is comfortable. But we should aim for O(n) since it's achievable with a hash map optimization.-3000 <= inorder[i], postorder[i] <= 3000→ Values can be negative, so we can't make assumptions about value ranges.- All values are unique → This is critical. It means we can locate any value's position in the inorder array unambiguously. Without this guarantee, reconstruction wouldn't be unique.
Approach 1: Recursive with Linear Search
Intuition
The most straightforward approach comes directly from understanding how the two traversals encode tree structure.
In postorder traversal (left, right, root), the last element is always the root. In inorder traversal (left, root, right), once we know the root, everything to its left is the left subtree and everything to its right is the right subtree. So the algorithm writes itself: take the last element of postorder as the root, find it in inorder to split the tree, and recurse.
The key question is: how do we figure out which part of the postorder array belongs to the left subtree vs. the right subtree? The answer is the size of the left subtree. If the root is at index rootIndex in the inorder array, and the inorder range starts at inStart, then the left subtree has rootIndex - inStart nodes. Those same nodes occupy the first rootIndex - inStart positions of the postorder segment (since postorder processes left before right).
Algorithm
- If the current range is empty (start > end), return null.
- Take the last element of the current postorder range as the root.
- Search for this root value in the inorder array (linear scan).
- Calculate the size of the left subtree from the root's position in inorder.
- Recursively build the left subtree using the left portions of both arrays.
- Recursively build the right subtree using the right portions of both arrays.
- Return the root node.
Example Walkthrough
Code
- Time Complexity: O(n^2). We make n recursive calls (one per node), and at each call we do a linear search through the inorder array to find the root, which takes O(n) in the worst case. So total work is O(n^2).
- Space Complexity: O(n). The recursion depth can be up to n for a completely skewed tree. Each stack frame uses O(1) space, so total is O(n).
This approach works correctly but the linear search at each step is redundant. The positions of values in the inorder array never change, so what if we precomputed them for O(1) lookups?
Approach 2: Recursive with Hash Map (Optimal)
Intuition
The algorithm from Approach 1 is already correct. The only inefficiency is the linear search for the root in the inorder array. Since all values are unique, we can build a hash map from value to index before we start the recursion. This turns every root lookup from O(n) to O(1), making the entire algorithm O(n).
The recursive logic stays exactly the same: the last element of the current postorder segment is the root, we look up its position in inorder to determine the left subtree size, and we split both arrays accordingly. The only difference is that the lookup is now a hash map query instead of a loop.
The correctness relies on two properties working together. First, the last element of any postorder segment is guaranteed to be the root of that subtree, because postorder processes children before the parent. Second, in the inorder array, the root separates the left and right subtrees. These two facts let us uniquely determine the tree structure.
The size calculation is the subtle but critical piece. Once we know the root sits at index rootIndex in the inorder array and our inorder range starts at inStart, the left subtree contains exactly rootIndex - inStart nodes. In the postorder array, those same nodes appear first (postorder visits left subtree, then right subtree, then root). So the left subtree's postorder range is [postStart, postStart + leftSize - 1], and the right subtree's postorder range is [postStart + leftSize, postEnd - 1] (excluding the root at postEnd).
Algorithm
- Build a hash map mapping each value in the inorder array to its index.
- Call the recursive build function with the full ranges of both arrays.
- At each recursive call, if the range is empty, return null.
- Take the last element of the current postorder range as the root.
- Look up the root's index in the inorder array using the hash map (O(1)).
- Calculate the left subtree size as
rootIndex - inStart. - Recursively build the left subtree and right subtree with the appropriate ranges.
- Return the root node.
Example Walkthrough
Code
- Time Complexity: O(n). Building the hash map takes O(n). Each of the n nodes is processed exactly once in the recursion, and the root lookup is O(1) per call. Total: O(n).
- Space Complexity: O(n). The hash map stores n entries, taking O(n) space. The recursion stack can be up to O(n) deep for a skewed tree. Total: O(n).