Use a queue to visit nodes level by level, left to right. Snapshot size = q.size() at the start of each iteration to process exactly one level at a time. The queue naturally enforces FIFO level ordering.
🌊 Level-by-Level📦 Queue (FIFO)🔢 Shortest Path to LeavesTime O(n)Space O(w)
📋 When to Use
Level-by-level output — collect all nodes per level, zigzag, averages
Shortest path / min depth — BFS guarantees shortest path in unweighted trees
Right/left side view — take first or last node of each level
Connect level pointers — populate next-right pointers level by level
Whenever depth or level index of each node matters
💡 The key trick is capturing int size = q.size() before the inner loop — this snapshot tells you exactly how many nodes belong to the current level, so you process them all before moving to the next.
⚡ Complexity
Time
O(n)
Space (queue)
O(w)
Where n = number of nodes, w = max width of tree (widest level).
Best case (skewed): O(1) queue space per level.
Worst case (perfect binary tree): last level has n/2 nodes → O(n) queue space.
Every node is enqueued and dequeued exactly once — O(n) time.
Live Animation · BFS Level Order Traversal · LC #102
Problem
Given a binary tree with 7 nodes (root = 1, level 1 = [2,3], level 2 = [4,5,6,7]), return each level's nodes grouped in a list. Use a queue and snapshot int size = q.size() before each inner loop to process exactly one level at a time.
Input: root = [1,2,3,4,5,6,7] · Answer: [[1],[2,3],[4,5,6,7]]
Step 0 / 11
🔧 Init📌 Process➕ Enqueue✔ Level Done✅ Done
🌊 BFS Level Order: use a Queue to visit nodes level by level. Enqueue the root, then for each level snapshot size = q.size() and process exactly that many nodes, enqueueing their children.
// BFS level-order skeleton
🌲 Binary Tree
processing
queued
done
default
📦 Queue (FIFO)
— empty —
front → back
🔢 Current Level:
[ — ]
📝 Result:
[ waiting... ]
🧩 Pattern Skeleton
Java 8
// BFS — Level Order TraversalList<List<Integer>> result = newArrayList<>();
if (root == null) return result;
Queue<TreeNode> q = newLinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // snapshot current level sizeList<Integer> level = newArrayList<>();
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);
}
result.add(level); // store completed level
}