150. Construct Binary Tree from Inorder and Postorder Traversal
🔗 LeetCode Problem: 106. Construct Binary Tree from Inorder and Postorder Traversal
📊 Difficulty: Medium
🏷️ Topics: Binary Trees, Array, Divide and Conquer, Recursion, HashMap
Problem Statement
Given two integer arrays inorder and postorder where:
- inorder is the inorder traversal of a binary tree
- postorder is the postorder traversal of the same tree
Construct and return the binary tree.
Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Constraints:
- 1 <= inorder.length <= 3000
- postorder.length == inorder.length
- -3000 <= inorder[i], postorder[i] <= 3000
- inorder and postorder consist of unique values
- Each value of postorder also appears in inorder
- inorder is guaranteed to be the inorder traversal of the tree
- postorder is guaranteed to be the postorder traversal of the tree
🌳 Visual Understanding - Comparing with Preorder
Traversal Comparison:
PREORDER (Root → Left → Right):
[Root, ...Left..., ...Right...]
↑
ROOT at START
POSTORDER (Left → Right → Root):
[...Left..., ...Right..., Root]
↑
ROOT at END
INORDER (Left → Root → Right):
[...Left..., Root, ...Right...]
↑
ROOT in MIDDLE (splits left/right)
Key difference: Root position! 🔑
Example - Visual Breakdown:
Given:
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
STEP 1: Find root from postorder
postorder[last] = 3
Root = 3 ✓
STEP 2: Find root in inorder
inorder = [9, | 3 |, 15, 20, 7]
↑ ↑ ↑
left root right
STEP 3: Partition inorder
Left subtree: [9]
Right subtree: [15, 20, 7]
STEP 4: Partition postorder accordingly
Left: [9] (first 1 element)
Right: [15, 7, 20] (next 3 elements)
Root: [3] (last element)
STEP 5: Current tree structure
3
/ \
? ?
/ \
[9] [15,20,7]
Recursively build left and right!
Visual Comparison with Preorder Problem:
PROBLEM 149 (Preorder + Inorder):
preorder = [3, 9, 20, 15, 7]
↑ ↑ ↑---------↑
root left right
Root at START
PROBLEM 150 (Inorder + Postorder):
postorder = [9, 15, 7, 20, 3]
↑ ↑---------↑ ↑
left right root
Root at END
BOTH: Inorder splits left/right
DIFFERENCE: Where to find root! 🎯
🧠 The AHA Moment - Same Pattern, Different Root!
The Core Algorithm:
buildTree(inorder, postorder):
1. Root = postorder[LAST] ← KEY DIFFERENCE!
2. Find root index in inorder
3. Elements before root in inorder = left subtree
4. Elements after root in inorder = right subtree
5. Partition postorder based on sizes
6. Recursively build left and right subtrees
7. Connect and return
Almost IDENTICAL to Problem 149! ✨
Visual Algorithm Flow:
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
┌────────────────────────────────────┐
│ Find root: postorder[LAST] = 3 │
│ Find in inorder: index 1 │
│ │
│ Partition inorder: │
│ Left: [9] (indices 0-0) │
│ Right: [15,20,7] (indices 2-4) │
│ │
│ Partition postorder: │
│ Left size = 1 │
│ Left: [9] (indices 0-0) │
│ Right: [15,7,20] (indices 1-3) │
│ Root: [3] (index 4) │
└────────────────────────────────────┘
↓
Recurse on left and right
🧠 Recursive Thinking - Building the Solution
Base Case:
When to stop?
→ When postorder or inorder range is empty
What to return?
→ null (no tree)
if (postStart > postEnd) return null;
// OR
if (inStart > inEnd) return null;
Recursive Case:
For any valid range:
STEP 1: Create root from postorder LAST
int rootVal = postorder[postEnd]; ← KEY!
TreeNode root = new TreeNode(rootVal);
STEP 2: Find root in inorder
int rootIndex = inorderMap.get(rootVal);
STEP 3: Calculate left subtree size
int leftSize = rootIndex - inStart;
STEP 4: Recursively build left subtree
root.left = buildTree(
inorder, inStart, rootIndex - 1,
postorder, postStart, postStart + leftSize - 1
);
STEP 5: Recursively build right subtree
root.right = buildTree(
inorder, rootIndex + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1
);
STEP 6: Return constructed root
return root;
Key Differences from Preorder:
PREORDER (Problem 149):
Root = preorder[preStart] (FIRST)
Left: [preStart+1 to preStart+leftSize]
Right: [preStart+leftSize+1 to preEnd]
POSTORDER (Problem 150):
Root = postorder[postEnd] (LAST)
Left: [postStart to postStart+leftSize-1]
Right: [postStart+leftSize to postEnd-1]
Same logic, different indices! 🎯
🎯 Solution: Divide and Conquer with HashMap
Implementation:
class Solution {
private Map<Integer, Integer> inorderMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
// Build hashmap for O(1) lookup of root in inorder
// WHY? Same reason as Problem 149
inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
// Start recursive building
return build(inorder, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}
private TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
// Base case: no elements to construct tree
if (inStart > inEnd || postStart > postEnd) {
return null;
}
// STEP 1: Last element in postorder is root
// WHY? Postorder visits root LAST! (Left→Right→Root)
int rootVal = postorder[postEnd];
TreeNode root = new TreeNode(rootVal);
// STEP 2: Find root position in inorder
// WHY? Same as preorder - inorder splits left/right
int rootIndex = inorderMap.get(rootVal);
// STEP 3: Calculate left subtree size
// WHY? Need to know how to partition postorder
int leftSize = rootIndex - inStart;
// STEP 4: Recursively build left subtree
// Inorder: elements before root
// Postorder: first 'leftSize' elements (left comes before right in postorder)
root.left = build(inorder, inStart, rootIndex - 1,
postorder, postStart, postStart + leftSize - 1);
// STEP 5: Recursively build right subtree
// Inorder: elements after root
// Postorder: middle section (after left, before root)
root.right = build(inorder, rootIndex + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1);
// STEP 6: Return constructed subtree
return root;
}
}
Postorder Index Logic:
postorder = [Left elements, Right elements, Root]
↑-----------↑ ↑-------------↑ ↑
leftSize rightSize 1
If leftSize = 2:
postorder indices:
Left: [postStart to postStart+1] (2 elements)
Right: [postStart+2 to postEnd-1] (remaining before root)
Root: [postEnd] (last element)
Key: Right goes up to postEnd-1 (exclude root!) 🔑
🔍 Detailed Dry Run - Complete Recursion
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
inorderMap = {9:0, 3:1, 15:2, 20:3, 7:4}
Complete Call Stack Visualization:
═══════════════════════════════════════════════════
CALL STACK - BUILDING THE TREE
═══════════════════════════════════════════════════
Level 0: build(in[0-4], post[0-4])
│
├─ rootVal = postorder[4] = 3 ← LAST element!
├─ Create node: TreeNode(3)
├─ rootIndex = inorderMap.get(3) = 1
├─ leftSize = 1 - 0 = 1
│
├─ LEFT: build(in[0-0], post[0-0]) ──────────────┐
│ │
│ Level 1: build(in[0-0], post[0-0]) │
│ │ │
│ ├─ inStart=0, inEnd=0 │
│ ├─ postStart=0, postEnd=0 │
│ │ │
│ ├─ rootVal = postorder[0] = 9 │
│ ├─ Create node: TreeNode(9) │
│ ├─ rootIndex = inorderMap.get(9) = 0 │
│ ├─ leftSize = 0 - 0 = 0 │
│ │ │
│ ├─ LEFT: build(in[0--1], post[0--1]) │
│ │ → inStart > inEnd → return null │
│ │ │
│ ├─ RIGHT: build(in[1-0], post[0--1]) │
│ │ → inStart > inEnd → return null │
│ │ │
│ └─ return TreeNode(9) │
│ └─ Node structure: 9 │
│ / \ │
│ null null │
│ │
├─ 3.left = TreeNode(9) │
│ │
├─ RIGHT: build(in[2-4], post[1-3]) ──────────────┐
│ │
│ Level 1: build(in[2-4], post[1-3]) │
│ │ │
│ ├─ inStart=2, inEnd=4 │
│ ├─ postStart=1, postEnd=3 │
│ │ │
│ ├─ rootVal = postorder[3] = 20 ← LAST! │
│ ├─ Create node: TreeNode(20) │
│ ├─ rootIndex = inorderMap.get(20) = 3 │
│ ├─ leftSize = 3 - 2 = 1 │
│ │ │
│ ├─ LEFT: build(in[2-2], post[1-1]) ─────┐ │
│ │ │ │
│ │ Level 2: build(in[2-2], post[1-1]) │ │
│ │ │ │ │
│ │ ├─ rootVal = postorder[1] = 15 │ │
│ │ ├─ Create node: TreeNode(15) │ │
│ │ ├─ rootIndex = 2 │ │
│ │ ├─ leftSize = 0 │ │
│ │ │ │ │
│ │ ├─ LEFT: null │ │
│ │ ├─ RIGHT: null │ │
│ │ │ │ │
│ │ └─ return TreeNode(15) │ │
│ │ │ │
│ ├─ 20.left = TreeNode(15) │ │
│ │ │
│ ├─ RIGHT: build(in[4-4], post[2-2]) ─────┐ │
│ │ │ │
│ │ Level 2: build(in[4-4], post[2-2]) │ │
│ │ │ │ │
│ │ ├─ rootVal = postorder[2] = 7 │ │
│ │ ├─ Create node: TreeNode(7) │ │
│ │ ├─ rootIndex = 4 │ │
│ │ ├─ leftSize = 0 │ │
│ │ │ │ │
│ │ ├─ LEFT: null │ │
│ │ ├─ RIGHT: null │ │
│ │ │ │ │
│ │ └─ return TreeNode(7) │ │
│ │ │ │
│ ├─ 20.right = TreeNode(7) │ │
│ │ │
│ └─ return TreeNode(20) │
│ └─ Node structure: 20 │
│ / \ │
│ 15 7 │
│ │
├─ 3.right = TreeNode(20) │
│ │
└─ return TreeNode(3) │
└─ Final tree: 3 │
/ \ │
9 20 │
/ \ │
15 7 │
═══════════════════════════════════════════════════
FINAL RESULT: Complete binary tree constructed! ✓
═══════════════════════════════════════════════════
Postorder Processing Order:
postorder = [9, 15, 7, 20, 3]
↑ ↑ ↑ ↑ ↑
1 2 3 4 5 (order processed)
Process backwards:
1st: Root 3 (index 4)
2nd: Root of right (20) (index 3)
3rd: Root of right-right (7) (index 2)
4th: Root of right-left (15) (index 1)
5th: Root of left (9) (index 0)
We process RIGHT before LEFT in recursive calls!
But within postorder array, LEFT comes before RIGHT!
🔍 Visual Index Calculations
Understanding Postorder Partitioning:
Given:
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
↑
idx 4 (root)
At root (3):
rootIndex in inorder = 1
inStart = 0
leftSize = rootIndex - inStart = 1 - 0 = 1
Postorder partitioning:
Left: postorder[0 to 0+leftSize-1]
= postorder[0 to 0]
= [9]
Right: postorder[0+leftSize to end-1]
= postorder[1 to 3]
= [15, 7, 20]
Root: postorder[end]
= postorder[4]
= [3]
Inorder partitioning:
Left: inorder[0 to rootIndex-1]
= inorder[0 to 0]
= [9]
Right: inorder[rootIndex+1 to end]
= inorder[2 to 4]
= [15, 20, 7]
Comparison with Preorder:
PREORDER + INORDER:
preorder = [3, 9, 20, 15, 7]
↑ ↑ ↑---------↑
root L Right
Left: [preStart+1 to preStart+leftSize]
Right: [preStart+leftSize+1 to preEnd]
POSTORDER + INORDER:
postorder = [9, 15, 7, 20, 3]
↑ ↑---------↑ ↑
L Right root
Left: [postStart to postStart+leftSize-1]
Right: [postStart+leftSize to postEnd-1]
Mirror image! 🪞
📊 Complexity Analysis
Time Complexity: O(n)
HashMap construction: O(n)
Recursive construction: O(n)
Visit each node once
O(1) lookup per node
Total: O(n) ✓
Space Complexity: O(n)
HashMap: O(n)
Recursion stack: O(h)
Best: O(log n)
Worst: O(n)
Total: O(n)
⚠️ Common Mistakes
Mistake 1: Using preStart Instead of postEnd for Root
// ❌ WRONG - Using first element like preorder
int rootVal = postorder[postStart]; // WRONG!
// Postorder visits root LAST, not first!
// ✓ CORRECT - Use last element
int rootVal = postorder[postEnd]; ✓
Mistake 2: Wrong Right Subtree Range
// ❌ WRONG - Not excluding root
root.right = build(inorder, rootIndex + 1, inEnd,
postorder, postStart + leftSize, postEnd); // Includes root!
// Problem: postEnd is the ROOT!
// Right subtree should end at postEnd-1
// ✓ CORRECT - Exclude root (postEnd-1)
root.right = build(inorder, rootIndex + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1); ✓
Mistake 3: Wrong Left Subtree Range
// ❌ WRONG - Off by one
root.left = build(inorder, inStart, rootIndex - 1,
postorder, postStart, postStart + leftSize); // One too many!
// Problem: Should be leftSize-1 elements
// [postStart to postStart+leftSize] = leftSize+1 elements!
// ✓ CORRECT - Use leftSize-1
root.left = build(inorder, inStart, rootIndex - 1,
postorder, postStart, postStart + leftSize - 1); ✓
Mistake 4: Processing Order Confusion
// ❌ CONCEPTUAL ERROR - Thinking we process left first
// "Postorder is left-right-root, so I process left first in recursion"
// WRONG THINKING! The array is left-right-root,
// but we BUILD from root (which is at END)!
// We find root at END, then recursively build:
// 1. Left subtree (from left part of postorder)
// 2. Right subtree (from right part of postorder)
// The ARRAY order ≠ BUILDING order!
Mistake 5: Not Understanding Index Mapping
// ❌ WRONG - Copying preorder logic exactly
root.left = build(inorder, inStart, rootIndex - 1,
postorder, postStart + 1, postStart + leftSize); // WRONG!
// Problem: This is preorder logic (skip first for root)
// In postorder, root is at END, not START!
// ✓ CORRECT - Start from postStart (no skip needed)
root.left = build(inorder, inStart, rootIndex - 1,
postorder, postStart, postStart + leftSize - 1); ✓
🎯 Pattern Recognition - Reconstruction Variations
All Reconstruction Patterns:
1. Preorder + Inorder (Problem 149):
Root = preorder[START]
Left: [START+1 to START+leftSize]
Right: [START+leftSize+1 to END]
2. Postorder + Inorder (Problem 150):
Root = postorder[END]
Left: [START to START+leftSize-1]
Right: [START+leftSize to END-1]
3. Preorder only (BST):
Use value comparison
Smaller than root → left
Larger than root → right
Core pattern: Find root, partition, recurse! 🎯
Why Some Combinations Don't Work:
❌ Preorder + Postorder (NO INORDER):
Can't uniquely determine tree!
Example:
pre = [1, 2]
post = [2, 1]
Could be: 1 OR 1
/ \
2 2
Need inorder to split left/right!
✓ Any traversal + Inorder = Unique tree
✓ Preorder only works for BST (has order property)
📝 Quick Revision Notes
🎯 Core Concept
Build tree from inorder and postorder arrays. Postorder gives root (LAST element), inorder partitions left/right. Almost identical to Problem 149, but root at END instead of START. Use HashMap for O(1) lookup. Calculate leftSize to partition correctly. Key difference: postorder ranges must exclude root at end.
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
int postorderStart = 0;
int postorderEnd = postorder.length - 1;
int inorderStart = 0;
int inorderEnd = inorder.length - 1;
HashMap<Integer, Integer> inorderMap = new HashMap<>();
for(int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return buildTree(postorderStart, postorderEnd, inorderStart, inorderEnd, inorderMap, postorder, inorder);
}
private TreeNode buildTree(int postorderStart, int postorderEnd, int inorderStart, int inorderEnd,
HashMap<Integer,Integer> inorderMap, int[] postorder, int[] inorder) {
// base case - boundary checks
if(postorderStart > postorderEnd || inorderStart > inorderEnd) { // CHANGE
return null; // this case should never exist and may exist for leaf nodes. Returns null.
}
// step 1: always end element of the postorder array is the root element.
// why postorderEnd instead of 0? It will not be always 0 as we divide array more number of subarrays later in the future.
int rootElement = postorder[postorderEnd];
// Get index of root element in inorder array.
// It is guaranteed that all elements are unique.
// Element before this rootElementIndex belong to LST and after this rootElementIndex belong to RST.
int rootElementIndex = inorderMap.get(rootElement);
// Step 2: Initialize root with root element and constrct LST and RST.
TreeNode root = new TreeNode(rootElement);
// Step 3: This is the ONLY GOTCHA of this whole problem. How much (size of LST) I have to take in preorder array is the main issue?
// This is not the issue with inorder array as root element index already decides that.
int leftSubtreeSize = rootElementIndex - inorderStart;
// Step 4: Construct LST with the remains of preorder and inorder arrays.
// All are intuitive if you put on paper except a little care on leftSubtreeSize.
// CHANGE: postorderStart, postorderStart + leftSubtreeSize - 1 since element is taken at the end now.
root.left = buildTree(postorderStart, postorderStart + leftSubtreeSize - 1, inorderStart, rootElementIndex - 1, inorderMap, postorder, inorder);
// Step 5: Construct RST with the remains of preorder and inorder arrays.
// All are intuitive if you put on paper
// CHANGE: postorderStart + leftSubtreeSize, postorderEnd - 1 since element is taken at the end now.
root.right = buildTree(postorderStart + leftSubtreeSize, postorderEnd - 1, rootElementIndex + 1, inorderEnd, inorderMap, postorder, inorder);
return root;
}
public static void main(String[] args) {
Solution s = new Solution();
TreeNode res1 = s.buildTree(new int[] {9,3,15,20,7}, new int[] {9,15,7,20,3});
TreeNode.print(res1);
}
}
🔑 Key Insights
Postorder vs Preorder:
PREORDER (Problem 149):
[Root, ...Left..., ...Right...]
↑
Root at START → use preorder[preStart]
POSTORDER (Problem 150):
[...Left..., ...Right..., Root]
↑
Root at END → use postorder[postEnd]
Everything else SAME! 🎯
Critical Index Differences:
PREORDER:
root.left: pre[preStart+1 to preStart+leftSize]
root.right: pre[preStart+leftSize+1 to preEnd]
POSTORDER:
root.left: post[postStart to postStart+leftSize-1]
root.right: post[postStart+leftSize to postEnd-1]
Key: Right subtree ends at postEnd-1 (exclude root!)
The Postorder Structure:
postorder = [Left subtree, Right subtree, Root]
If leftSize = 2, postStart = 0, postEnd = 5:
Left: [0, 1] (2 elements)
Right: [2, 4] (remaining before root)
Root: [5] (last element)
Always: right ends at postEnd-1! 🔑
Why Inorder is Essential:
Both preorder and postorder need inorder to:
- Find root position
- Split left vs right subtrees
- Determine subtree sizes
Inorder is the KEY to reconstruction! 🗝️
🎪 Memory Aid
"Postorder root at END, not start!"
"Right ends at postEnd-1 (skip root)!"
"Left: postStart to postStart+leftSize-1!"
"Same pattern as preorder, different indices!" ✨
⚠️ Don't Forget
- Root from postEnd (LAST, not first!)
- Right ends at postEnd-1 (exclude root!)
- Left ends at postStart+leftSize-1 (not +leftSize!)
- HashMap for O(1) (same optimization!)
- Same logic as Problem 149 (just different indices!)
- Inorder still splits left/right (unchanged!)
🎉 Congratulations!
You've mastered both reconstruction patterns!
What You Learned:
✅ Postorder properties - Root at end
✅ Index arithmetic - Different from preorder
✅ Pattern similarity - Same algorithm
✅ Critical differences - Root location
✅ Reconstruction mastery - Both variations
✅ Problem comparison - Understanding differences
The Connection:
Problem 149 vs Problem 150:
SAME:
- Inorder for left/right split
- HashMap optimization
- leftSize calculation
- Divide and conquer
- O(n) complexity
DIFFERENT:
- Root position (start vs end)
- Index ranges for subtrees
- Array partitioning details
Learn one → Know both! 🎯
Interview Mastery:
Interviewer: "Build tree from inorder and postorder"
Your response:
"Very similar to preorder + inorder!
Key difference: Root at END of postorder
(Postorder: Left → Right → Root)
Algorithm:
1. Root = postorder[last]
2. Find root in inorder → split left/right
3. Calculate leftSize
4. Recursively build with correct ranges
Critical: Right ends at postEnd-1 (exclude root)
Time: O(n), Space: O(n)"
Shows pattern recognition! 💯
You've mastered tree reconstruction from traversals! 🏆✨🎯