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.

                    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.

Output: 1 2 3 4 5

Case 3. Tree having just one node

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.

/* C Program for level order traversal of a Tree */

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
struct node
```
```
{
```
```
    int info; 
```
```
    struct node *left, *right; 
```
```
}; 
```
```
struct node *createnode(int key)
```
```
{
```

    struct node *newnode = (struct node*)malloc(sizeof(struct node));

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
    return(newnode);
```
```
}
```
```
/*
```

 * Function to ascertain the height of a Tree

```
 */
```
```
int heightoftree(struct node *root)
```
```
{
```
```
    int max;
```
```
    if (root!=NULL)
```
```
    {
```

        /* Finding the height of left subtree. */

        int leftsubtree = heightoftree(root->left);

        /* Finding the height of right subtree. */

        int rightsubtree = heightoftree(root->right);

```
        if (leftsubtree > rightsubtree)
```
```
        {
```
```
            max = leftsubtree + 1;
```
```
            return max;
```
```
        }
```
```
        else
```
```
        {
```
```
            max = rightsubtree + 1;
```
```
            return max;
```
```
        }
```
```
    }
```
```
}
```
```
/*
```

 * Function to print all the nodes left to right of the current level

```
 */
```

void currentlevel(struct node *root, int level)

```
{
```
```
    if (root != NULL) 
```
```
    {
```
```
        if (level == 1)
```
```
        {
```
```
            printf("%d ", root->info);
```
```
        }
```
```
        else if (level > 1) 
```
```
        { 
```

            currentlevel(root->left, level-1);

            currentlevel(root->right, level-1);

```
        }			
```
```
    }
```
```
}
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main() 
```
```
{   
```
```
   /* Creating first Tree. */
```

    struct node *newnode = createnode(25);

```
    newnode->left = createnode(27); 
```
```
    newnode->right = createnode(19); 
```

    newnode->left->left = createnode(17);

    newnode->left->right = createnode(91);

    newnode->right->left = createnode(13);

    newnode->right->right = createnode(55);

```
    /* Sample Tree 1:
```
```
     *                25
```
```
     *             /    \  
```
```
     *            27     19   
```
```
     *           / \     / \ 
```
```
     *         17  91   13 55 
```
```
     */
```

    printf("Level Order Traversal of Tree 1 is \n");

```
    int i;
```
```
    int height = heightoftree(newnode);
```

    /* Calling current level function, by passing levels one by one. */

```
    for(i = 1; i <= height; i++)      
```
```
    {
```
```
        currentlevel(newnode,i);
```
```
    }
```
```
 
```
```
    /* Creating second Tree. */ 
```
```
    struct node *node = createnode(1);
```
```
    node->right = createnode(2);
```
```
    node->right->right = createnode(3);
```

    node->right->right->right = createnode(4);

    node->right->right->right->right = createnode(5);

    /* Sample Tree 2:   Right Skewed Tree (Unbalanced).

```
     *               1   
```
```
     *                \
```
```
     *                 2    
```
```
     *                  \    
```
```
     *                   3 
```
```
     *                    \
```
```
     *                     4
```
```
     *                      \
```
```
     *                       5
```
```
     */
```

    printf("\n\nLevel Order Traversal of Tree 2 is \n");

```
    height = heightoftree(node);
```

    /* Calling current level function, by passing levels one by one. */

```
    for(i = 1; i <= height; i++)    
```
```
    { 
```
```
        currentlevel(node,i);
```
```
    }
```
```
 
```
```
    /* Creating third Tree. */
```

    struct node *root = createnode(15);

    /* Sample Tree 3- Tree having just one root node.

     *              15

```
     */
```

    printf("\n\nLevel Order Traversal of Tree 3 is \n");

```
    height = heightoftree(root);
```

    /* calling current level function, by passing levels one by one. */

```
    for(i = 1; i <= height; i++)    
```
```
    {
```
```
        currentlevel(root,i);
```
```
    }                      
```
```
    return 0; 
```
```
}
```

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

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

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

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

« Prev - C Program to Implement Hash Tables Chaining with Doubly Linked Lists

» Next - Spiral Order Traversal of a Tree using Recursion

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Check Programming Books
Check Data Structure Books
Practice Computer Science MCQs
Check Computer Science Books

Recommended Articles: