Construct the Binary Tree from Postorder and Inorder Traversal
HardPostorder gives the root, read from the end
Problem
Build a binary tree from its postorder and inorder traversals.
Postorder's last value is the root; its position in inorder splits the subtrees — recurse right first.
The idea
The last postorder value is the root; locating it in the inorder array splits the subtrees exactly as before. Because you consume postorder from the back, build the right subtree before the left.
The trick
- Take roots from the end of postorder.
- Build right first, then left, to keep the indices aligned.
- Same O(1) inorder index map, same O(n).
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — post=[9,15,7,20,3], in=[9,3,15,20,7] Values: 9, 15, 7, 20, 3.
1root = post[last]; find it in inorder at m2right = build first (postorder ends with right subtree), then leftInput
- array
- [9, 15, 7, 20, 3]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
- Output:
- [[3], [9, 20], [15, 7]]
- Explanation:
- Rebuild the tree from these two orders.
Example 2
- Input:
- inorder = [2,1], postorder = [2,1]
- Output:
- [[1], [2]]
- Explanation:
- 2 is the left child of 1.
Example 3
- Input:
- inorder = [1], postorder = [1]
- Output:
- [[1]]
- Explanation:
- Single node.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.