Level Order Traversal of a Tree using Recursion in C++

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.

                    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
advertisement

Case 3. Tree having just one node

                    15

Output: 15

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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.

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);

advertisement

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”.

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.

advertisement
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 Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.