Tree BFS (Level Order)
The Intuition
Fire alarm goes off in a building. Floor 1 evacuates first. Every single person on floor 1 walks out before anyone on floor 2 even starts moving. Once floor 1 is clear, floor 2 goes. Then floor 3. You never have someone from floor 5 leaving while floor 2 is still occupied.
A queue makes this happen naturally. Everyone on floor 1 is in the queue. You process them one by one, and as you process each person, you add their "neighbors on the next floor" (their children in tree terms) to the back of the queue. By the time you finish everyone from floor 1, the queue contains exactly the people from floor 2. Nothing else. Process them, and now the queue has floor 3. The queue acts as a perfect separator between levels.
The one critical detail: you have to snapshot the queue's size before you start processing a level. Say the queue has 4 nodes. Those 4 are your current level. You process exactly 4, and during that processing you might add 6 children to the queue. If you don't capture that "4" upfront, you'll accidentally start processing the next level's nodes as part of the current level. Capture the size, loop exactly that many times, and the level boundaries stay clean.
That's why BFS gives you level-order traversal for free. The queue guarantees breadth-first processing. Want the right-side view? Just grab the last node from each level. Want zigzag order? Alternate the direction you read each level's results. Want level averages? Sum each level and divide by its size. All of these are just variations on the same core loop.
Level-order traversal, zigzag traversal, right/left side view, level averages, minimum depth, connecting level-order siblings, or any problem requiring per-level grouping.
- Need path from root to a specific node (use DFS)
- Need to process leaves before parents (use DFS postorder)
- Memory is tight and tree is very wide (BFS queue grows with width)
Variations:
- Standard level order: Collect values grouped by level.
- Zigzag order: Alternate left-to-right and right-to-left per level.
- Right-side view: Take the last node of each level.
- Level averages: Compute the average value at each depth.
- empty tree
- single node
- complete vs sparse tree
Key Points
- •Use a queue to process nodes level by level
- •Track level boundaries using queue size at each level
- •Width w is the maximum number of nodes at any level (up to n/2)
- •Can collect values per level into sublists
- •Useful for zigzag, right-side view, and average-per-level problems
Code Template
1 from collections import deque
2
3 def level_order(root):
4 """Level-order traversal returning list of levels."""
5 if not root:
6 return []
7 result = []
8 queue = deque([root])
9
10 while queue:
11 level_size = len(queue)
12 level = []
13 for _ in range(level_size):
14 node = queue.popleft()
15 level.append(node.val)
16 if node.left:
17 queue.append(node.left)
18 if node.right:
19 queue.append(node.right)
20 result.append(level)
21
22 return result
23
24 def right_side_view(root):
25 """Right-side view: last node of each level."""
26 if not root:
27 return []
28 result = []
29 queue = deque([root])
30
31 while queue:
32 level_size = len(queue)
33 for i in range(level_size):
34 node = queue.popleft()
35 if i == level_size - 1:
36 result.append(node.val)
37 if node.left:
38 queue.append(node.left)
39 if node.right:
40 queue.append(node.right)
41
42 return resultCommon Mistakes
- Not capturing queue size before processing the level
- Mixing up BFS level processing with regular queue drain
- Forgetting to handle empty tree (null root)