Module 6 · Tree Construction

Construct Binary Tree from Inorder and Postorder Traversal

MediumProblem 19 of 24 9 min read ~25 min to solve LeetCode

TreeDepth-First SearchDivide and ConquerHash TableRecursion

Asked atAmazonMicrosoftGoogleMetaAdobe

Problem Statement

Given two integer arrays inorder and postorder, where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the original binary tree.

All values are unique, so the inorder position of each root value is unambiguous.

Input

Two arrays: inorder, which visits left, root, right, and postorder, which visits left, right, root.

Output

The root of the reconstructed binary tree described by both traversals.

Constraints

•1 <= inorder.length <= 3000
•postorder.length == inorder.length
•-3000 <= inorder[i], postorder[i] <= 3000
•All values in inorder and postorder are unique
•inorder and postorder describe the same binary tree

Examples

Example 1

Input:

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

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

Explanation: The last postorder value 3 is the root. In inorder, 3 splits the left subtree [9] from the right subtree [15,20,7]. Moving backward through postorder sees the right subtree root 20 before the left subtree root 9.

Example 2

Input:

inorder = [-1], postorder = [-1]

Output: [-1]

Explanation: A single traversal value creates a single-node tree.

Learning Objectives

Explain why the last unused postorder value is the root of the current subtree.
Build from the end of postorder without reversing the array.
Understand why the right subtree must be built before the left subtree.
Use inorder boundaries and a hash map to reconstruct in linear time.

Intuition

Pattern Recognition

The pair inorder + postorder is the mirror image of the preorder reconstruction problem. Postorder visits left, right, root, so the last value of a subtree is its root. Inorder still gives the split: once you know the root, values left of it belong to the left subtree and values right of it belong to the right subtree.

The ordering subtlety is the whole interview trap. If you consume postorder from the end, after taking the root you encounter the right subtree before the left subtree. Therefore the recursive construction must attach root.right before root.left. Building left first will consume values from the wrong side and produce an invalid tree.

Common mistakes

×Building the left subtree before the right subtree while moving backward through postorder.
×Using the first postorder value as the root instead of the last unused value.
×Scanning inorder repeatedly instead of using a hash map.
×Passing full arrays to every call and accidentally mixing subtree boundaries.

Algorithm Explanation

Key idea

The last unused postorder value is the root of the current subtree. Find that value in the current inorder window to split left and right. Because we are moving backward through postorder, build the right subtree first, then the left subtree.

Recursion walkthrough

Use inorder [9,3,15,20,7] and postorder [9,15,7,20,3]. The last postorder value is 3, so 3 is the root. In inorder, 3 splits the tree into left side [9] and right side [15,20,7]. Moving backward, the next postorder value is 20, which belongs to the right side. In inorder, 20 splits [15,20,7] into left child [15] and right child [7]. Because backward postorder sees right before left, 7 is built before 15. Only after the right subtree is finished do we build the left subtree rooted at 9.

Algorithm

Build a hash map from each inorder value to its index.
Set postorderIndex to postorder.length - 1.
Define a recursive helper over an inorder window left..right.
If the window is empty, return null.
Read postorder[postorderIndex] as the root value, then decrement postorderIndex.
Look up the root's inorder index to split the current window.
Recursively build the right subtree from the right window first.
Recursively build the left subtree from the left window second.
Return the root node.

Solutions

Solution: Reverse postorder pointer plus inorder index map

When to prefer this:

Use this when inorder and postorder traversals are available and values are unique. It is the direct linear-time construction and highlights the right-before-left ordering subtlety.

Precompute value -> inorder index. Keep postorderIndex at the end of postorder. Each recursive call owns an inorder range. The current postorder value is the root for that range, the map gives the split, and the helper must build the right range before the left range because postorder is being consumed backward.

Step-by-step

Store every inorder value's index in a hash map.
Start postorderIndex at the final position of postorder.
Return null for an empty inorder range.
Choose postorder[postorderIndex] as the root and move the pointer left.
Split the current inorder range around the root.
Build the right child first from the right range.
Build the left child second from the left range.
Return the root after both children are attached.

Time

O(n)

Space

O(n)

The hash map stores n indices and each node is created once. The recursion stack is O(h), which can be O(n) for a skewed tree.

Java implementation

Loading…

Dry Run

Sample input

inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]. Track the roots consumed from the end of postorder.

call	root	inorder window	right inorder	left inorder
build(0,4)	3	[9,3,15,20,7]	[15,20,7]	[9]
build(2,4)	20	[15,20,7]	[7]	[15]
build(4,4)	7	[7]	empty	empty
build(2,2)	15	[15]	empty	empty
build(0,0)	9	[9]	empty	empty

The root sequence from the back of postorder is 3, 20, 7, 15, 9. That order proves why the right subtree must be constructed before the left subtree.

Interview Tips

After explaining that postorder's last value is the root, immediately mention the subtle mirror step: when walking backward, build right before left. Many wrong solutions are identical to preorder construction except for pointer direction, and that is not enough. Also call out that inorder remains the splitter in both reconstruction problems.

Likely follow-ups

What would break if you built the left subtree before the right subtree?
Can you derive an iterative stack-based reconstruction?
How would duplicates change the uniqueness guarantee?
How would you reconstruct a tree if you were given preorder and postorder instead?

Key Takeaways

Postorder's last unused value is the current subtree root.
Inorder still splits that root into left and right subtree ranges.
When consuming postorder backward, construct right before left.
The same hash-map and boundary technique keeps reconstruction O(n).

Reusable template: Reverse traversal reconstruction: consume roots from the end of postorder, split with inorder, and recurse right before left.