A Queue of Waiting Nodes

We need to hold the nodes we have discovered but not yet visited, and always take the one we met earliest next. A queue does that: we enqueue at the back and dequeue from the front, so the first node in is the first one out.

The plan

Put the root in an empty queue. Then repeat these steps until the queue is empty:

• dequeue a node from the front,
• visit it, and
• enqueue its children, left then right, at the back.

There is no recursion here, only a loop. The queue holds the waiting nodes that recursion kept on the call stack.

Tracing the plan

Here is our tree again.

                  ╭───╮
                  │ 5 │
                  ╰─┬─╯
         ┌──────────┴──────────┐
       ╭─┴─╮                 ╭─┴─╮
       │ 8 │                 │ 2 │
       ╰─┬─╯                 ╰─┬─╯
    ┌────┴────┐           ┌────┴────┐
  ╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
  │ 9 │     │ 1 │       │ 4 │     │ 7 │
  ╰─┬─╯     ╰───╯       ╰───╯     ╰─┬─╯
  ┌─┘                               └─┐
╭─┴─╮                               ╭─┴─╮
│ 6 │                               │ 3 │
╰───╯                               ╰───╯

The queue is shown with its front at the left and its back at the right.

start: enqueue 5:

┌───┐
│ 5 │
└───┘
  ▲
front, back

dequeue 5 → visit 5, enqueue 8 and 2:

┌───┬───┐
│ 8 │ 2 │
└───┴───┘
  ▲   ▲
front back

dequeue 8 → visit 8, enqueue 9 and 1:

┌───┬───┬───┐
│ 2 │ 9 │ 1 │
└───┴───┴───┘
  ▲       ▲
front   back

dequeue 2 → visit 2, enqueue 4 and 7:

┌───┬───┬───┬───┐
│ 9 │ 1 │ 4 │ 7 │
└───┴───┴───┴───┘
  ▲           ▲
front       back

dequeue 9 → visit 9, enqueue 6:

┌───┬───┬───┬───┐
│ 1 │ 4 │ 7 │ 6 │
└───┴───┴───┴───┘
  ▲           ▲
front       back

dequeue 1 → visit 1:

┌───┬───┬───┐
│ 4 │ 7 │ 6 │
└───┴───┴───┘
  ▲       ▲
front   back

dequeue 4 → visit 4:

┌───┬───┐
│ 7 │ 6 │
└───┴───┘
  ▲   ▲
front back

dequeue 7 → visit 7, enqueue 3:

┌───┬───┐
│ 6 │ 3 │
└───┴───┘
  ▲   ▲
front back

dequeue 6 → visit 6:

┌───┐
│ 3 │
└───┘
  ▲
front, back

dequeue 3 → visit 3:

(empty queue)

Reading the visits in order gives 5 8 2 9 1 4 7 6 3, the level-order we read off the tree level by level.

Why it comes out level by level

It comes out level by level for the same reason the maze’s queue search takes every cell one move from the start before any cell two moves out. When we visit a node and enqueue its children, those children go to the back, behind every node already waiting. So every node on one level comes out before any node on the next level. The left-to-right order within a level is preserved because we always enqueue the left child before the right, and the queue returns them in that same order.