Problem Description
C++ Program for Level Order Traversal of a given Tree using Recursion.
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.
Problem Source Code
#include <iostream>
#include<stdio.h>
using namespace std;
struct node
int info;
struct node* left, *right;
}*root;
class BST
public:
struct node * createnode(int key);
int heightoftree(struct node* root);
void currentlevel(struct node* root, int level);
BST()
root=NULL;
};
/*
* Main Function
*/
int main()
BST b1;
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);
cout<<"Level Order traversal of the Tree is\n"<<endl;
int i;
int height = b1.heightoftree(newnode);
for(i = 1; i <= height; i++) //calling current level function, by passing levels one by one in an
increasing order.
b1.currentlevel(newnode,i);
return 0;
struct node* BST:: 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 BST :: heightoftree(struct node* root)
int max;
if (root!=NULL)
int leftsubtree = heightoftree(root->left); //Finding the height of left subtree.
int rightsubtree = heightoftree(root->right); //Finding the height of right subtree.
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 BST :: 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 Case
Level Order traversal of the Tree is
25 27 19 17 91 13 55
