Level order traversal is different from other more common types of tree traversal algorithms such as in-order, pre-order or post-order. Level order traversal visits the nodes level by level. Once it’s done with the root (level 0) it moves to level 1, then to level 2, e.t.c. Perhaps the two most major differences between level-order traversal and the other 3 algorithms are that:

1. It is an iterative algorithm
2. It makes use of an extra data structure, a FIFO queue.

The reason why we need to use a queue is because we have no easy way of travelling backwards in a tree.

For example, in the following tree, if we are at the node with value 2, it may be easy to go to node number 5, but what about node 8?

(Node-2 and Node-8 belong to different subtrees, accessing one from the other requires going backwards)

The only node that connects these two nodes (formally called the Lowest Common Ancestor) is node number 6, the root of the tree. Now imagine a very deep tree with countless of leaves and the problem gets downright impossible.

That’s where the queue comes into play. The algorithm is pretty simple.

1. Push the root into the queue
2. While the queue is not empty
3. 1. Pop a node from the queue (Remember a queue works in a First-In First-Out way)
   2. Do something with its data
   3. Push its children into the queue
4. By the time the queue is empty, the algorithm will have visited all nodes

Let’s apply level-order traversal to the above tree to visit and print all of its nodes. We start with a queue that only contains the root of the tree.

Queue: node-6
Output:

First loop (Level 0)

We begin by taking the first element out of the queue, which of course is the root of the tree. We print its value to the output and push its children into the queue

Queue: node-6, ode-4
Output: 6

Second loop (Level 1)

We take node-9 out of the queue, print its value and push its two children into the queue

Queue: node-4, node-2, node-5
Output: 6, 9

Third loop (Level 1)

We take node-4 out of the queue, print its value and push its right child into the queue

Queue: node-2, node-5, node-8
Output: 6, 9, 4

Fourth loop (Level 2)

We take node-2 out of the queue. Node-2 does not have any children so nothing gets pushed to the queue. We just print “2”.

Queue: node-5, node-8
Output: 6, 9, 4, 2

Fifth loop (Level 2)

We take node-5 out of the queue. Node-5 has no children nodes so we just print its value and move on

Queue: node-8
Output: 6, 9, 4, 2, 5

Sixth loop (Level 2)

We take node-8 out of the queue. Node-8 has no children nodes, so we print “8” and then notice that the queue is empty. So the sixth loop is the final one and we’ve managed to print all elements of the tree in a level-order from left to right.

Queue:
Output: 6, 9, 4, 2, 5, 8

Now to the C++ implementation of the algorithm:

Each node is described by the following struct:

And here’s the levelOrderTraversal function

The C++ Standard Library provides a FIFO queue out of the box accessible to you by including the header. However you can still use a custom implementation of it if you like .