C Program for Level Order Traversal of a 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 is equal on both the sides of root.

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 just have 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

advertisement
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 */ 
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. struct node
  5. {
  6.     int info; 
  7.     struct node *left, *right; 
  8. }; 
  9. struct node *createnode(int key)
  10. {
  11.     struct node *newnode = (struct node*)malloc(sizeof(struct node));
  12.     newnode->info = key;
  13.     newnode->left = NULL;
  14.     newnode->right = NULL;
  15.     return(newnode);
  16. }
  17. /*
  18.  * Function to ascertain the height of a Tree
  19.  */
  20. int heightoftree(struct node *root)
  21. {
  22.     int max;
  23.     if (root!=NULL)
  24.     {
  25.         /* Finding the height of left subtree. */
  26.         int leftsubtree = heightoftree(root->left);
  27.         /* Finding the height of right subtree. */
  28.         int rightsubtree = heightoftree(root->right);
  29.         if (leftsubtree > rightsubtree)
  30.         {
  31.             max = leftsubtree + 1;
  32.             return max;
  33.         }
  34.         else
  35.         {
  36.             max = rightsubtree + 1;
  37.             return max;
  38.         }
  39.     }
  40. }
  41. /*
  42.  * Function to print all the nodes left to right of the current level
  43.  */
  44. void currentlevel(struct node *root, int level)
  45. {
  46.     if (root != NULL) 
  47.     {
  48.         if (level == 1)
  49.         {
  50.             printf("%d ", root->info);
  51.         }
  52.         else if (level > 1) 
  53.         { 
  54.             currentlevel(root->left, level-1); 
  55.             currentlevel(root->right, level-1);
  56.         }			
  57.     }
  58. }
  59. /*
  60.  * Main Function
  61.  */
  62. int main() 
  63. {   
  64.    /* Creating first Tree. */
  65.     struct node *newnode = createnode(25); 
  66.     newnode->left = createnode(27); 
  67.     newnode->right = createnode(19); 
  68.     newnode->left->left = createnode(17); 
  69.     newnode->left->right = createnode(91);
  70.     newnode->right->left = createnode(13);
  71.     newnode->right->right = createnode(55);	
  72.     /* Sample Tree 1:
  73.      *                25
  74.      *             /    \  
  75.      *            27     19   
  76.      *           / \     / \ 
  77.      *         17  91   13 55 
  78.      */
  79.     printf("Level Order Traversal of Tree 1 is \n");	
  80.     int i;
  81.     int height = heightoftree(newnode);
  82.     /* Calling current level function, by passing levels one by one. */
  83.     for(i = 1; i <= height; i++)      
  84.     {
  85.         currentlevel(newnode,i);
  86.     }
  87.  
  88.     /* Creating second Tree. */ 
  89.     struct node *node = createnode(1);
  90.     node->right = createnode(2);
  91.     node->right->right = createnode(3);
  92.     node->right->right->right = createnode(4);
  93.     node->right->right->right->right = createnode(5);
  94.     /* Sample Tree 2:   Right Skewed Tree (Unbalanced).
  95.      *               1   
  96.      *                \
  97.      *                 2    
  98.      *                  \    
  99.      *                   3 
  100.      *                    \
  101.      *                     4
  102.      *                      \
  103.      *                       5
  104.      */
  105.     printf("\n\nLevel Order Traversal of Tree 2 is \n");
  106.     height = heightoftree(node);
  107.     /* Calling current level function, by passing levels one by one. */
  108.     for(i = 1; i <= height; i++)    
  109.     { 
  110.         currentlevel(node,i);
  111.     }
  112.  
  113.     /* Creating third Tree. */
  114.     struct node *root = createnode(15); 
  115.     /* Sample Tree 3- Tree having just one root node.
  116.      *              15                 
  117.      */
  118.     printf("\n\nLevel Order Traversal of Tree 3 is \n");
  119.     height = heightoftree(root);
  120.     /* calling current level function, by passing levels one by one. */
  121.     for(i = 1; i <= height; i++)    
  122.     {
  123.         currentlevel(root,i);
  124.     }                      
  125.     return 0; 
  126. }
Program Explanation

Program contains three important functions.

advertisement

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

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.

advertisement

Here’s the list of Best Reference Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
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 | Youtube | Instagram | Facebook | Twitter