How does a breadth-first traversal work, and why does it need a queue?

Breadth-first visits all nodes of depth $t$ before any node of depth $t + 1$, level by level. It keeps the nodes still to be visited in a queue: dequeue a node, visit it, enqueue its children. Because the queue is FIFO, children always wait behind every node of the current level.

* The dashed path is the visiting order: across each level, then down to the next. *

Algorithm breadthFirst()
  initialize queue Q containing root
  while Q not empty do
    v = Q.dequeue()
    visit(v)
    for each child w in children(v) do
      Q.enqueue(w)

Why a queue, and not recursion like the other traversals? Recursion follows one branch all the way down before returning, which is depth-first by nature. Breadth-first has to jump across the tree: after the root's children it must visit their children, which live in different subtrees.

The queue makes that work. When a node at depth $t$ is visited, its children (depth $t+1$) join the back of the queue, behind every depth-$t$ node still waiting. So the queue always serves an entire level before the next one. Each node is enqueued and dequeued once: $O(n)$.

Tip: preorder and postorder are "depth-first" and use the call stack; breadth-first uses a queue. Stack versus queue is the whole difference.

Go deeper:

• Breadth-first search — the same queue-driven idea on general graphs, where it finds shortest paths.