Level Order Traversal II
Mahabharata — The Inverted Hierarchy — From Leaf Warriors to the Commander at Last
नीचे से ऊपर — पत्तियां पहले, मूल अंत में। BFS करो — फिर पलट दो॥
*Bottom to top — leaves first, root at the end. Do BFS — then reverse.*
The Story
Return nodes level by level from bottom to top (leaf level first, root level last).
For tree `[3,9,20,15,7]`: [[15,7],[9,20],[3]].
This is almost identical to tr-4 (Level Order), with one change: collect levels in reverse order.
**Three approaches:**
**1. BFS + reverse result:** ```java // Same as tr-4, then: Collections.reverse(res); ```
**2. BFS with addFirst:** ```java LinkedList<List<Integer>> res = new LinkedList<>(); // ... same BFS ... res.addFirst(level); // Instead of res.add(level) ``` Each level is prepended, resulting in bottom-up order.
**3. DFS with depth:** Same DFS from tr-4, but use `res.addFirst(...)` or sort by level descending.
The addFirst approach is the cleanest: ```java LinkedList<List<Integer>> res = new LinkedList<>(); Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int size=q.size(); List<Integer> level=new ArrayList<>(); for (int i=0;i<size;i++) { TreeNode node=q.poll(); level.add(node.val); if(node.left!=null) q.offer(node.left); if(node.right!=null) q.offer(node.right); } res.addFirst(level); // KEY: prepend each level } ```
This builds the result list from bottom to top by inserting each new (deeper) level at the front.
The BFS + Collections.reverse Approach
Regular level order BFS, then reverse the entire result list. O(n).
public List<List<Integer>> levelOrderBottomBrute(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
// ... standard BFS from tr-4 ...
Collections.reverse(res);
return res;
}The BFS-addFirst Wisdom
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> res = new LinkedList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = q.poll();
level.add(node.val);
if (node.left != null) q.offer(node.left);
if (node.right != null) q.offer(node.right);
}
res.addFirst(level); // Prepend: deeper levels go first
}
return res;
}Step-by-Step Walkthrough
Single node [1]: q=[1]. size=1. level=[1]. addFirst([1]). res=[[1]] ✅
Deep Insight
**The addFirst trick:** By inserting each level at the FRONT of the LinkedList, later-visited (deeper) levels end up at the front. After BFS completes, the list is in bottom-up order.
**vs Collections.reverse:** Both are O(n). The addFirst approach is more elegant and avoids the separate reversal step. The reverse approach is more readable.
**This pattern:** 'Collect in order X, reverse to get order Y' appears frequently. Often addFirst/addLast is cleaner than collecting in order then reversing.
**Connection to tr-3 (Postorder):** Both use addFirst to build results in reverse order. Postorder uses addFirst on a LinkedList while collecting in a 'reverse-preorder' manner.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | BFS + reverse |
| Optimal | O(n) | O(n) | BFS with addFirst — no separate reverse needed |
Pattern Recognition
✅ Level order bottom = BFS + addFirst instead of add ✅ Or: standard level order + Collections.reverse ✅ LinkedList needed for O(1) addFirst ✅ Result: deepest level first, root level last **LeetCode Trigger Phrases:** → "level order traversal II" bottom-up → BFS with reversed result → addFirst to build bottom-up order
Bhagavad Gita 15.1
ऊर्ध्वमूलमधःशाखमश्वत्थं प्राहुरव्ययम्।
With roots above and branches below, they speak of the imperishable Ashvattha tree.
Connection: The bottom-up level order traversal mirrors the inverted Ashvattha tree described in the Gita — the roots are above (the root of the BST, visited last) and the branches below (the leaves, visited first). The BFS explores from the root downward, but the addFirst operation inverts this to present the deepest levels first — reading the tree from its earthly branches up to its heavenly root.