Level Order Traversal LIne by Line code in c++.

Given a Tree and we need to print the level order traversal of the tree in slight different manner. Here level order traversal need to be printed line by line

For Example  in the diagram below

The output of program for above example is

A
B C
D E F G
H I

We have already discussed the level order traversal in the following post.

 Level Order Traversal

Kindly refer to it for detailed explanation

Code:-

[code language=”cpp”]

#include<bits/stdc++.h>

struct Treenode// definition of structure of tree node which has lchild child and rchild child
{
int val;
Treenode* lchild;
Treenode* rchild;
};

struct Treenode* newNode(int key)// function for new node creation
{
struct Treenode* newnode = (struct Treenode*)malloc(sizeof(struct Treenode));
newnode->val = key;
newnode->lchild = NULL;
newnode->rchild = NULL;

return(newnode);
}

// a function that prints the level order in desired form
void printLevelOrder(Treenode *root)
{
// Base Case
if (root == NULL) return;

// Create an empty queue for level order tarversal
queue<node *> q;

q.push(root);

while (1)
{

int Count = q.size();
if (Count == 0)
break;

while (Count > 0)
{
Treenode *temp = q.front();
cout << temp->val << " ";
q.pop();
if (temp->lchild != NULL)
q.push(temp->lchild);
if (temp->rchild != NULL)
q.push(temp->rchild);
Count–;
}
cout << endl;
}
}

int main()
{
Treenode *root1 = newNode(232);
Treenode *root2 = newNode(232);// these part is concerned with creation of tree
// user can edit this as per wish
root1->lchild = newNode(231);
root1->rchild = newNode(231);
root1->lchild->lchild = newNode(431);
root1->lchild->rchild = newNode(531);

root2->lchild = newNode(231);
root2->rchild = newNode(331);
root2->lchild->lchild = newNode(431);
root2->lchild->rchild = newNode(513);

levelorderlinebyline(root)

getchar();
return 0;
}

[/code]