Traverse a Binary Tree Level by Level

A queue hands back the nodes of one level before any node of the next.

A level-order traversal visits a tree's nodes one level at a time, from the root down and from left to right within each level, where a level is the set of nodes at the same depth. This card covers how a queue, the first-in, first-out list, produces that order, and traces it step by step on the tree used throughout this topic.

Level order is breadth-first: it visits every node at one depth before any node deeper down. The pre-, in- and post-order traversals are depth-first, finishing a whole subtree before moving on, and recursion cannot give level order because the call stack always finishes the deepest call first, while a queue can. The method has two rules. Start with the root alone in the queue. Then, while the queue is not empty, take the node at the front, visit it, and add its children to the back, left child first.

The tree has the root 1 with children 2 and 3, node 2 with children 4 and 5, node 3 with only a right child, 6, and node 6 with only a left child, 7. An instrumented copy of the function printed the queue, front first, and the nodes visited, after each step.

The queue and the visited nodes after each step of a level-order traversal

Start

The root is the only node in the queue, and nothing has been visited.

text

queue, front first: 1
visited: nothing

Dequeue 1

1 leaves the front and is visited. Its children, 2 and 3, join the back, left first.

text

queue, front first: 2 3
visited: 1

Dequeue 2

2 is visited, and its children 4 and 5 join the back, behind 3. Every node of depth 1 is now ahead of every node of depth 2.

text

queue, front first: 3 4 5
visited: 1 2

Dequeue 3

3 is visited. It has only a right child, so 6 is the one node added.

text

queue, front first: 4 5 6
visited: 1 2 3

Dequeue 4

4 is a leaf, so it is visited and nothing is added.

text

queue, front first: 5 6
visited: 1 2 3 4

Dequeue 5

5 is a leaf too, and the queue shrinks again.

text

queue, front first: 6
visited: 1 2 3 4 5

Dequeue 6

6 is visited, and its left child 7 joins the back of the queue, which held nothing else.

text

queue, front first: 7
visited: 1 2 3 4 5 6

Dequeue 7

7 is a leaf. The queue is empty, so the traversal stops with every node visited once.

text

queue, front first: empty
visited: 1 2 3 4 5 6 7

The order comes from when nodes join the queue. A node joins when its parent is visited, and parents are visited level by level, so every node of one level joins the back before any node of the next level does. First in, first out then hands them back in that order. With a stack in its place, the newest node would come out first, and the traversal would run down one branch before finishing a level, giving a depth-first order instead.

To know where each level ends, for example to print one level per line, read the queue's length when a level starts and take exactly that many nodes before starting the next. Each node joins and leaves the queue once, so a tree of n nodes takes O(n) time. The queue holds at most about one level and part of the next, and in a tree whose levels are all full that is the bottom level, roughly half the nodes.

← → move through sections and cards