Recursive Level Order Traversal of a tree

Level order traversal is also called  breadth first traversal for the tree.

Non-Recursive solution of the problem is – Non-recursive Level Order Traversal

Approach:
There are basically two functions in this method. One is to print all nodes at a given level (printLevel), and other is to get height of tree and print level wise nodes.

struct node
{
    int data;
    struct node* left;
    struct node* right;
};

void printGivenLevel(struct node* root, int level);
int height(struct node* node);
 
/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
	int h = height(root);
	int i;
	for(i=1; i<=h; i++)
		printLevel(root, i);
}     
 
/* Print nodes at a given level */
void printLevel(struct node* root, int level)
{
	if(root == NULL)
		return;
	if(level == 1)
		printf("%d ", root->data);
	else if (level > 1)
	{
		printLevel(root->left, level-1);
		printLevel(root->right, level-1);
	}
}
 
/* Compute the "height" of a tree */
int height(struct node* node)
{
   if (node==NULL)
       return 0;
   else
   {
     int lheight = height(node->left);
     int rheight = height(node->right);
 
     if (lheight > rheight)
         return(lheight+1);
     else 
		return(rheight+1);
   }
} 

Time Complexity: O(n^2) in worst case. For a skewed tree

2 Thoughts on “Recursive Level Order Traversal of a tree

  1. Anonymous on June 3, 2014 at 7:10 pm said:

    why height+1

  2. Abhishek on February 8, 2015 at 7:40 am said:

    Considering the root node. Since the root node is part of both the left and the right subtree.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation