C++ Program for Level Order Traversal of a given Tree using Recursion

«
»

This is a C++ Program for Level Order Traversal of a Tree using Recursion.

Problem Description

Here in this problem we will be traversing the nodes of tree from left to right level by level. First the nodes at level 1 will be printed followed by the level two and so on. This problem is implemented using C++ programming language by recursion method.

Expected Input and Output

Case 1. Balanced Tree: When the weight on both the sides of the root node is same.

advertisement
                    25
                  /    \  
                 27     19   
                / \     / \ 
              17  91   13 55

Output: 25 27 19 17 91 13 55

Case 2. Right Skewed Tree: When the nodes at every level have just a right child.

                    1   
                     \
                      2    
                       \    
                        3 
                         \
                          4
                           \
                            5

Output: 1 2 3 4 5

advertisement

Case 3. Tree having just one node

                    15

Output: 15

Problem Solution

In order to find level order traversal of any tree using recursion, just find out the height of the tree and call the function which will print all the nodes in a level. currentlevel function prints all the nodes in a level, so it must be called as many times as the height of tree so as to cover all the levels from top to bottom.

advertisement
Program/Source Code

Here is source code of the C++ Program for level order traversal of a tree using recursion. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.

  1. /* C++ Program for level order traversal of a tree using recursion */
  2. #include <iostream>
  3. #include<stdio.h>
  4. using namespace std;
  5. struct node
  6. {
  7.     int info;
  8.     struct node *left, *right;
  9. };
  10. class Tree
  11. {
  12. public:
  13.     struct node *root;
  14.     struct node  *createnode(int key);
  15.     int heightoftree(struct node *newnode);
  16.     void currentlevel(struct node *root, int level);
  17.     Tree()
  18.     {
  19.         root = NULL;
  20.     }
  21. };
  22. /*
  23.  * Main Function
  24.  */
  25. int main()
  26. {   Tree b1;
  27.     /* Creating First Tree. */
  28.     struct node *newnode = b1.createnode(25);
  29.     newnode->left = b1.createnode(27);
  30.     newnode->right = b1.createnode(19);
  31.     newnode->left->left = b1.createnode(17);
  32.     newnode->left->right = b1.createnode(91);
  33.     newnode->right->left = b1.createnode(13);
  34.     newnode->right->right = b1.createnode(55);
  35.     /* Sample Tree 1: Balanced Tree
  36.      *               25
  37.      *             /    \
  38.      *            27     19
  39.      *           / \     / \
  40.      *         17  91   13 55
  41.      */
  42.     cout<<"Level Order Traversal of Tree 1 is \n";
  43.     int i;
  44.     int height = b1.heightoftree(newnode);
  45.     for(i = 1; i <= height; i++)
  46.     {
  47.         b1.currentlevel(newnode,i);
  48.     }
  49.  
  50.     /* Creating Second Tree */
  51.     struct node *node = b1.createnode(1);
  52.     node->left = b1.createnode(2);
  53.     node->left->left = b1.createnode(3);
  54.     node->left->left->left = b1.createnode(4);
  55.     node->left->left->left->left = b1.createnode(5);
  56.     /* Sample Tree 2- Left Skewed Tree
  57.      *                 1
  58.      *                /
  59.      *               2
  60.      *              /
  61.      *             3
  62.      *            /
  63.      *           4
  64.      *          /
  65.      *         5
  66.      */
  67.     cout<<"\n\nLevel Order Traversal of Tree 2 is \n";
  68.     height = b1.heightoftree(node);
  69.     for(i = 1; i <= height; i++)
  70.     {
  71.         b1.currentlevel(node,i);
  72.     }
  73.  
  74.     /* Creating Third Tree */
  75.     struct node *root = b1.createnode(15);
  76.     /* Sample Tree 3- Tree having just one root node.
  77.      *              15
  78.      */
  79.     cout<<"\n\nLevel Order Traversal of Tree 3 is \n";
  80.     height = b1.heightoftree(root);
  81.     for(i = 1; i <= height; i++)
  82.     {
  83.         b1.currentlevel(root,i);
  84.     }
  85.     return 0;
  86. }
  87. /*
  88.  * Function to create nodes
  89.  */
  90. struct node *Tree :: createnode(int key)
  91. {
  92.     struct node *newnode = new node;
  93.     newnode->info = key;
  94.     newnode->left = NULL;
  95.     newnode->right = NULL;
  96.     return(newnode);
  97. }
  98. /*
  99.  * Function to ascertain the height of a Tree
  100.  */
  101. int Tree :: heightoftree(struct node *root)
  102. {
  103.     int max;
  104.     if (root!=NULL)
  105.     {   
  106.         /* Finding the height of left subtree. */
  107.         int leftsubtree = heightoftree(root->left);
  108.         /* Finding the height of right subtree. */
  109.         int rightsubtree = heightoftree(root->right);
  110.         if (leftsubtree > rightsubtree)
  111.         {
  112.             max = leftsubtree + 1;
  113.             return max;
  114.         }
  115.         else
  116.         {
  117.             max = rightsubtree + 1;
  118.             return max;
  119.         }
  120.     }
  121. }
  122. /*
  123.  * Function to print all the nodes left to right of the current level
  124.  */
  125. void Tree :: currentlevel(struct node *root, int level)
  126. {
  127.     if (root != NULL)
  128.     {
  129.         if (level == 1)
  130.         {
  131.             cout<<root->info<<"\t";
  132.         }
  133.         else if (level > 1)
  134.         {
  135.             currentlevel(root->left, level-1);
  136.             currentlevel(root->right, level-1);
  137.         }
  138.     }
  139. }
Program Explanation

Program contains three important functions.

1. createnode(key);

This function helps to create a new node by allocating it a memory dynamically. It has just one parameter which is “key” which assigns value to the node thereby creating a fresh node having left and right child as “NULL”.

advertisement

2. heightoftree(newnode);

This function is used to find the height of a tree, by just passing the root node of a Tree. We call this function recursively by first passing newnode->left as root node to find the height of left subtree and then repeating it again for the right subtree.

3. currentlevel(root, level);

The most important function of the whole program. Once we find out the height of a tree, we call this function inside a loop as many times as the height of the tree. This function takes in two parameters and prints the nodes in a level which is passed in as one of the parameters, from left to right. If the level will be = 1 it will print the data of the root node, otherwise if level is greater than 1 it will first recursively call left node of the root node and then right node of the root node and in both the cases the level which was passed in parameters will be decreased by one.
Since we need to print all the levels in a tree, that is why we call this function in a loop and increase the level one by one.

Runtime Test Cases
Level Order Traversal of Tree 1 is
25      27      19      17      91      13      55
 
Level Order Traversal of Tree 2 is
1       2       3       4       5
 
Level Order Traversal of Tree 3 is
15

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Here’s the list of Best Reference Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn