Level order traversal is different from other more common types of tree traversal algorithms such as inorder, preorder or postorder. 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 levelorder traversal and the other 3 algorithms are that:
 It is an iterative algorithm
 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?
(Node2 and Node8 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.
 Push the root into the queue
 While the queue is not empty

 Pop a node from the queue (Remember a queue works in a FirstIn FirstOut way)
 Do something with its data
 Push its children into the queue
 By the time the queue is empty, the algorithm will have visited all nodes
Let’s apply levelorder 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: node6
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: node6, ode4
Output: 6
Second loop (Level 1)
We take node9 out of the queue, print its value and push its two children into the queue
Queue: node4, node2, node5
Output: 6, 9
Third loop (Level 1)
We take node4 out of the queue, print its value and push its right child into the queue
Queue: node2, node5, node8
Output: 6, 9, 4
Fourth loop (Level 2)
We take node2 out of the queue. Node2 does not have any children so nothing gets pushed to the queue. We just print “2”.
Queue: node5, node8
Output: 6, 9, 4, 2
Fifth loop (Level 2)
We take node5 out of the queue. Node5 has no children nodes so we just print its value and move on
Queue: node8
Output: 6, 9, 4, 2, 5
Sixth loop (Level 2)
We take node8 out of the queue. Node8 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 levelorder 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 .