Level Order Traversal is one of the methods for traversing across a Binary Tree. In this article, we shall look at how we can implement this algorithm in C/C++.
But before that, let us have our concepts covered.
A Binary Tree is a data structure where every node has at-most two children. The topmost node is called the Root node.
There are 4 common ways of traversing the nodes of a Binary Tree, namely:
Let’s understand what a level in a Binary Tree means.
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, for the root node (topmost node), it’s level is 0, since it has no parents. If it has children, both of them will have a level of 1, since it has only one ancestor until the root node, which is the root node itself.
We also need to understand the notion of height in a Binary Tree. This is simply the length of the path from the root to the deepest node in the tree.
In this case, the height will be the length from the deepest node (40 or 50, since they have the maximum level) to the root. So the height of the tree is 2.
Now that we have our concepts covered, let’s understand how we can implement Level Order Traversal.
A Level Order Traversal is a traversal which always traverses based on the level of the tree.
So, this traversal first traverses the nodes corresponding to Level 0, and then Level 1, and so on, from the root node.
In the example Binary Tree above, the level order traversal will be:
(Root) 10 -> 20 -> 30 -> 40 -> 50
To do this, we need to do 2 things.
We will find the height of the tree first. To do this, the logic is simple.
Since the height of the tree is defined as the largest path from the root to a leaf. So we can recursively compute the height of the left and right sub-trees, and find the maximum height of the sub-tree. The height of the tree will then simply be the height of the sub-tree + 1.
C- style Pseudo Code:
Now that we have the height, we must print nodes for every level. To do this, we will use a for
loop to iterate all levels until the height, and print nodes at every level.
Observe that we need another function to print the i
th level of the tree.
Here again, we have a similar logic. But this time, after printing the root node, we change the root node to it’s left and right children and print both sub-trees.
This will continue until we reach a leaf node, that is when the auxiliary root will be NULL
at the next step. (Since leaf_node->left = NULL
and leaf_node->right = NULL
)
Now, we have finally completed the Level Order Traversal!
I will provide the complete program below, which also has a section to construct the Binary Tree using insertion.
While this is originally a C program, the same can be compiled on C++ as well.
Output
You can also download this through a Github gist that I created for this purpose. (Contains code for insertion as well)
Hopefully you have a better understanding of how Level Order Traversal can be implemented in C/C++. If you have any questions, feel free to ask them in the comments section below!
Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.
While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.