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.

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 using recursion */

```
#include <iostream>
```
```
#include<stdio.h>
```
```
using namespace std;
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *left, *right;
```
```
};
```
```
class Tree
```
```
{
```
```
public:
```
```
    struct node *root;
```
```
    struct node  *createnode(int key);
```

    int heightoftree(struct node *newnode);

    void currentlevel(struct node *root, int level);

```
    Tree()
```
```
    {
```
```
        root = NULL;
```
```
    }
```
```
};
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main()
```
```
{   Tree b1;
```
```
    /* Creating First Tree. */
```

    struct node *newnode = b1.createnode(25);

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

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

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

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

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

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

    cout<<"Level Order Traversal of Tree 1 is \n";

```
    int i;
```

    int height = b1.heightoftree(newnode);

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

    struct node *node = b1.createnode(1);

```
    node->left = b1.createnode(2);
```

    node->left->left = b1.createnode(3);

    node->left->left->left = b1.createnode(4);

    node->left->left->left->left = b1.createnode(5);

```
    /* Sample Tree 2- Left Skewed Tree
```
```
     *                 1
```
```
     *                /
```
```
     *               2
```
```
     *              /
```
```
     *             3
```
```
     *            /
```
```
     *           4
```
```
     *          /
```
```
     *         5
```
```
     */
```

    cout<<"\n\nLevel Order Traversal of Tree 2 is \n";

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

    struct node *root = b1.createnode(15);

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

```
     *              15
```
```
     */
```

    cout<<"\n\nLevel Order Traversal of Tree 3 is \n";

```
    height = b1.heightoftree(root);
```
```
    for(i = 1; i <= height; i++)
```
```
    {
```
```
        b1.currentlevel(root,i);
```
```
    }
```
```
    return 0;
```
```
}
```
```
/*
```
```
 * Function to create nodes
```
```
 */
```

struct node *Tree :: createnode(int key)

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

 * Function to ascertain the height of a Tree

```
 */
```

int Tree :: 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 Tree :: currentlevel(struct node *root, int level)

```
{
```
```
    if (root != NULL)
```
```
    {
```
```
        if (level == 1)
```
```
        {
```
```
            cout<<root->info<<"\t";
```
```
        }
```
```
        else if (level > 1)
```
```
        {
```

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

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

```
        }
```
```
    }
```
```
}
```

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.

« Prev - C++ Program to Implement Interval Tree

» Next - C++ Program to Implement Double Order Traversal of a Binary Tree

Related Posts:

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

Recommended Articles: