Level-Order Traversal
What you'll learn: How to process graph or tree nodes level by level using markers or counters to separate each layer.
The Core Idea
Level-order traversal is a technique for visiting nodes in layers: first all nodes at distance 0 from the start, then all at distance 1, then distance 2, and so on. You've already learned BFS visits nodes layer-by-layer, but level-order traversal adds explicit tracking to know when one level ends and the next begins.
Think of it like organizing people at a concert by their distance from the stage. You want to process row 1, then row 2, then row 3—never mixing people from different rows together.
Tracking Levels: Two Common Approaches
1. Marker/Sentinel Method
After enqueuing all nodes at the current level, add a special marker (like null or a sentinel value) to the queue. When you dequeue this marker, you know the current level is complete.
2. Counter Method
Before processing each level, record how many nodes are currently in the queue—that's exactly how many nodes belong to this level. Process only that many nodes before moving to the next level.
Example (Counter Method):
Start: Queue = [A], Level 0
Process 1 node: A → enqueue B, C
Queue = [B, C], Level 1
Process 2 nodes: B, C → enqueue D, E, F
Queue = [D, E, F], Level 2
Each level is cleanly separated by counting queue size before processing.
When to Use It
Level-order traversal is essential when you need to:
- Print nodes by level
- Find the shortest path length (level = distance)
- Solve problems requiring layer-aware processing
Key Takeaway:
Level-order traversal processes nodes layer by layer by explicitly tracking level boundaries using either a marker/sentinel in the queue or a counter of nodes per level.