Level-order traversal — BFS with queue: Visual walkthrough

Step 1 — The wish: read a tree floor by floor

WHAT. A tree is a picture where one dot sits on top (the root), and lines drop down to children dots, which drop down to their children, and so on. A dot is a node. The level (also called depth) of a node is how many lines down from the root it sits: the root is level $0$ , its children are level $1$ , their children level $2$ .

WHY. Before we can invent an algorithm we must state exactly what output we want. Our wish is: print every node on level $0$ , then every node on level $1$ , then level $2$ … and left-to-right inside each floor. That word floor is the whole goal — everything else is machinery to achieve it.

PICTURE. Look at the tree below. The dashed horizontal bands are the floors. The desired reading order is the number written inside each node, and it sweeps each band left-to-right before dropping to the next.

Figure — Level-order traversal — BFS with queue

Step 2 — The obstacle: you can only see kids after you meet the parent

WHAT. When we stand on a node, the only new nodes we can "reach" are that node's own children. We cannot magically jump to a cousin two floors down — we discover the tree by walking its lines.

WHY. This is the crux. We want to output floor by floor, but we discover nodes parent-by-parent. So there is a gap between discovering a node and being ready to process it. Anything with a gap like that needs a place to park the discovered-but-not-yet-processed nodes. That parking lot is the data structure we are about to invent.

PICTURE. The red arrows show the only moves available from node 2: down-left to 4, down-right to 5. We found 4 and 5, but we are not allowed to print them yet — floor $1$ isn't finished (node 3 still waits). So 4 and 5 must go into a holding area (the grey box).

Step 3 — Which serving rule? FIFO vs LIFO, tested on the picture

WHAT. A parking lot for pending nodes can hand them back in one of two natural orders:

FIFO (First-In-First-Out): the one that arrived earliest leaves first. This is a queue — a polite line at a shop.
LIFO (Last-In-First-Out): the one that arrived most recently leaves first. This is a stack — a pile of plates.

WHY. We have to choose, and the choice is not free — it decides the whole output. So let's not guess; let's run both on the same tiny tree and watch. We enqueue the root, then repeatedly take one out, print it, and put its children in.

PICTURE. Two side-by-side traces on the same tree. On the left, FIFO serves 1, then 2, then 3 (floor $1$ finished!) before touching 4,5,6. On the right, LIFO serves 1, then dives straight into 3's side, printing 3 then 6 before it ever gets back to 2 — floors are shredded.

Step 4 — Prove FIFO really gives floors (the fence argument)

WHAT. We claim: with a queue, all of level $k$ comes out before any of level $k + 1$ . Let's see it, not just assert it.

WHY. "It looked right on one tree" is not a proof. We want to know it works on every tree. The picture below shows the key invariant: at the moment level $k$ is fully inside the queue, level $k + 1$ is completely absent — because level- $(k + 1)$ nodes are the children of level- $k$ nodes, and children only enter after their parent is served.

PICTURE. The queue is drawn as a horizontal line, front on the left. The yellow block is all of level $k$ , sitting contiguously. As we serve each yellow node from the front, its green children (level $k + 1$ ) append to the back — always behind every remaining yellow node. So the whole yellow block empties before a single green node reaches the front. A clean fence separates the floors.

Step 5 — The algorithm writes itself

WHAT. Steps 1–4 hand us the code with no further invention.

WHY. Each line below is a consequence we already justified: seed the root (Step 1), loop while pending nodes remain (Step 2), serve oldest = dequeue (Step 3 FIFO), append children to the back (Step 4 fence), guard None because empty spots have no children (Step 2 — you can only push real kids).

PICTURE. The flow of one iteration: pull from the front (blue), print it (yellow), push its children to the back (green).

Formula Flat level-order (BFS with a queue)

enqueue(root)
while queue not empty:
    node = dequeue()        # FRONT = oldest  (Step 3: FIFO)
    visit(node)             # print it        (the wish, Step 1)
    if node.left:  enqueue(node.left)   # push to BACK (Step 4 fence)
    if node.right: enqueue(node.right)  # guard None   (Step 2)

Step 6 — Grouping by floor: the size snapshot

WHAT. Flat BFS gives one long list. To get one list per floor (like [[1],[2,3],[4,5,6]]), we freeze the queue's length at the start of each round.

WHY. From Step 4 we know: at the start of a round, the queue holds exactly one floor. So its current length is that floor's node-count. If we record n = len(queue) before we start pulling, and then pull exactly n times, we drain precisely this floor — no more, no less — even though children are pouring into the back meanwhile.

PICTURE. The queue holds [2,3] (one full floor). We snapshot n = 2 (yellow bracket). We pull 2 (its kids 4,5 join the back) and pull 3 (its kid 6 joins the back). After exactly $n = 2$ pulls we stop: the queue now holds the next floor [4,5,6], untouched.

Formula Grouped BFS

enqueue(root)
while queue not empty:
    n = size(queue)         # snapshot: nodes on THIS floor (Step 4)
    level = []
    repeat n times:         # drain exactly this floor
        node = dequeue()
        level.append(node.val)
        if node.left:  enqueue(node.left)
        if node.right: enqueue(node.right)
    output.append(level)

$n$ — frozen floor-width. Freezing before the inner loop is the whole trick.
repeat n times — draws the fence from Step 4 in code form.

Step 7 — Edge & degenerate cases (never surprise the reader)

WHAT. We check the corners the happy path skipped.

WHY. An algorithm you trust must survive the weird inputs, not just the neat balanced tree.

PICTURE. Three corner trees and what the queue does in each.

Empty tree (root is None). We never enqueue anything; the while never runs; output is empty. Correct — no floors to read.
Single node. Enqueue 1, serve 1, it has no kids, queue empties. Output [1]. Max queue size $= 1$ .
Skewed tree (a straight line 1→2→3). Each floor has exactly one node, so the queue never holds more than one node at a time. Output 1 2 3. Here BFS uses $O (1)$ space — its worst space case is a wide tree, not a tall one.

The one-picture summary

Everything above compressed into a single frame: the tree on top, the queue as a moving line below, the fence sliding right one floor at a time, the printed output growing left-to-right.

Recall Feynman retelling — the whole walkthrough in plain words (click to reveal)

You want to read a family portrait one row at a time, left to right. Trouble is, you only meet someone's children after you meet them — so you keep a waiting line. You call the person at the front, write their name, and tell their kids "go stand at the back of the line." Because every new kid joins the back, you always finish calling a whole row before any of that row's kids reach the front — the rows never mix. That "front-out, back-in" rule is a queue (FIFO); a stack would call the newest kid first and send you diving down one branch instead. If you also want the names bundled by row, just count how many people are in line before you start a round — that count is exactly this row's size, so you call exactly that many and stop. Empty tree? The line starts empty, you do nothing. One node? One call. A straight line of nodes? The waiting line is never longer than one — which is why a queue costs memory proportional to the widest row, not the tallest branch.

Active recall

Recall Trace it yourself

Empty answers, then check. The gap that forces a container is between which two orderings? ::: Discovery order (parent-by-parent) and desired output order (floor-by-floor). What single equation fixes the serving rule to FIFO? ::: output order = serving order; demanding floor-by-floor output forces oldest-first. Why is level k fully served before level k+1 ever reaches the front? ::: Level k+1 are children, appended to the back only after their parents are served, so they sit behind all remaining level-k nodes (the fence). Why snapshot len(queue) before the inner grouped loop? ::: At round start the queue holds exactly one floor, so its length is that floor's width; freezing it drains exactly that floor despite incoming children. What determines BFS space, width or height, and why? ::: Width — the queue holds one floor at a time, so its size tracks the maximum level width w.

Connections

Parent: Level-order traversal — the full note this page illustrates.
Breadth-First Search (BFS) — the general algorithm; this is its tree case.
Depth-First Search (DFS) — the stack/LIFO counterpart we ruled out in Step 3.
Queue (FIFO) data structure — the parking lot we were forced to invent.
Stack (LIFO) — the tempting-but-wrong alternative.
Binary Tree representation — how the nodes and left/right children are stored.
Shortest path in unweighted graphs — same fence argument gives shortest distances.
Tree height vs width — why BFS space is width, DFS space is height.