Level Order Traversal
Mahabharata — The Council Tiers — Visiting Every Rank of Warriors Level by Level
स्तर-दर-स्तर — चौड़ाई से पहले। BFS से — प्रत्येक स्तर की सूची अलग॥
*Level by level — breadth before depth. BFS — each level's list is separate.*
The Story
Return nodes level by level: [[root], [level-1-nodes], [level-2-nodes], ...].
For tree `[3,9,20,null,null,15,7]`: [[3],[9,20],[15,7]].
**BFS with queue:** - Add root to queue - While queue not empty: process one full level at a time - Record queue size (= number of nodes at this level) - Dequeue `size` nodes, add to level list, enqueue their children - Add level list to result
```java Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int size = q.size(); // Number of nodes at current level 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.add(level); } ```
The key insight: at the start of each outer iteration, `q.size()` gives exactly the number of nodes at the current level. We process exactly that many, then the queue contains the next level.
Trace `[3,9,20]`: - q=[3], size=1. Process 3, add [3], enqueue 9,20. res=[[3]] - q=[9,20], size=2. Process 9,20, add [9,20], no children. res=[[3],[9,20]]
The DFS with Level Tracking
DFS carrying depth parameter. Add to res[depth]. O(n) time, O(n) space.
void dfsLevel(TreeNode root, int depth, List<List<Integer>> res) {
if (root == null) return;
if (depth >= res.size()) res.add(new ArrayList<>());
res.get(depth).add(root.val);
dfsLevel(root.left, depth+1, res);
dfsLevel(root.right, depth+1, res);
}The Queue Level-by-Level BFS Wisdom
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
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.add(level);
}
return res;
}Step-by-Step Walkthrough
Single node [1]: q=[1]. size=1. Process 1, level=[1]. No children. res=[[1]] ✅
Deep Insight
**The `size` snapshot trick:** At the start of each level, `q.size()` is exactly the number of nodes at that level. By capturing this before adding children, we process exactly one level per outer iteration.
**Level order variants:** - tr-5: ZigZag (alternate direction each level) - tr-6: Bottom-up (reverse the result) - Right side view: take last element of each level - Left/right side view, level averages, level max — all trivial BFS extensions
**DFS alternative:** The DFS with depth tracking is also O(n) and O(h) space (h=height). Prefer BFS for actual level-order output.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(n) | DFS with depth tracking |
| Optimal | O(n) | O(n) | Queue holds at most one full level = O(n) worst case |
Pattern Recognition
✅ Level order = BFS with queue ✅ size = q.size() at start of each level ✅ Process exactly size nodes per level ✅ Foundation for all level-based problems **LeetCode Trigger Phrases:** → "level order traversal" → BFS tree traversal level by level → Right side view / level averages / zigzag
Bhagavad Gita 11.12
दिवि सूर्यसहस्रस्य भवेद्युगपदुत्थिता। यदि भाः सदृशी सा स्याद्भासस्तस्य महात्मनः॥
If a thousand suns were to rise simultaneously in the sky, their radiance might be compared to the effulgence of that Supreme Person.
Connection: Level order traversal reveals the tree's structure tier by tier — like the morning sun illuminating each rank of Kurukshetra in turn, first the commanders at the front, then the mid-ranks, then the vast background formations. The BFS queue processes the divine tree level by level, breadth first, so no level is skipped or darkened before its turn comes to be fully illuminated.