[Data Structure] [Tree] Level Order Traversal - Best Method [C++]

Level Order Traversal is a traversal algorithm in Tree Data Structure, where a tree traversed from left to right for each level one by one.

So level order traversal first traverse the root node which is at level zero and then for level 1 and so on.

There are four way commonly used for traverse the binary tree:

• In Order
• Pre Order
• Post Order
• Level Order 

Let's understand what is level order in binary tree and how to traverse binary tree using Level Order Traversal.

A level is the number of parent nodes corresponding to a given a node of the tree. It is basically the number of ancestors from that node until the root node.

So, root node level is zero, since it has no parents. If it has two children, both children level would be 1, since it has only one ancestor until the root node, which is the root node itself.

Now, you should understand that what is level and how level order traversal traverse the binary tree. Lets take an example:

In the above figure, we start traveling level 0 i.e. root node.

Then goto level 1 and travel 4, 8 and so on...

So we travel in the order: 6, 4, 8, 2, 5, 7, 9, 3, 10

For implementation we need a queue data structure. to travel in level order

C++ implementation: