Lesson 16.3 · Binary Trees
Breadth-First: Level by Level
A queue processes the tree one level at a time; read the queue's size at the start of each level.
12 min
Think of it like this
Announcing exam results school year by school year: first everyone in year 1, then year 2, and so on. Within a year you go left to right along the row.
1.One loop per level
Put the root in a queue. While it's not empty, read size = queue.size(): exactly the nodes of the current level. Poll that many nodes, record them, and offer their children, which form the next level.
Levels make many questions easy: averages per level, the rightmost node per level (right side view), zigzag order, and minimum depth (the first leaf found).
root = [3, 9, 20, null, null, 15, 7]queue(queue)
levels(list)
empty
Step 1/4Level 0: the queue holds just 3 (size 1).
Remember
- Queue + level size = level-by-level processing.
- BFS finds the shallowest node first.
- Space is the width of the widest level.
Common mistakes
- Using queue.size() inside the inner loop condition (it changes as you offer children).