   # Print a binary tree from top to bottom in level order

+6 votes
243 views

Given binary tree is:

``````        1
/     \
2        3
/  \        \
4   5         6
/   \
7     8
``````

The output should be 1, 2, 3, 4, 5, 6, 7, 8 posted Jan 3, 2014
Share this question

## 2 Answers

+1 vote
``````#include<stdio.h>
#include<stdlib.h>

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

struct node *createnode(int k)
{
struct node *nwnode=malloc(sizeof(struct node));
nwnode->data=k;
nwnode->left=NULL;
nwnode->right=NULL;
return nwnode;
}

void PrintLevelNodeBottomUp(struct node *t)
{
if(t==NULL)
return;
struct node *List;
int m;
for(m=0;m<20;m++)
List[m]=NULL;
int i=0;
int j=0;
List[i++]=t;
struct node *pP=List;
List[i++]=createnode(-1);
while(pP!=NULL && List[j+1]!=NULL)
{
if(pP->right!=NULL && pP->data!=-1)
List[i++]=pP->right;
if(pP->left!=NULL && pP->data!=-1)
List[i++]=pP->left;
if(pP->data==-1)
List[i++]=createnode(-1);
pP=List[++j];
}
for(m=i-1;m>=0;m--)
{
if(List[m]->data==-1)
printf("\n");
else
printf("%d ",List[m]->data);
}
}

int main(int args,char *argv[])
{
root=createnode(11);
root->left=createnode(4);
root->right=createnode(15);
root->left->left=createnode(3);
root->left->right=createnode(8);
root->left->left->left=createnode(7);
root->left->left->left->left=createnode(1);
root->right->left=createnode(10);
root->right->right=createnode(16);
root->right->right->right=createnode(14);
root->right->left->left=createnode(5);
root->right->right->right->right=createnode(2);
PrintLevelNodeBottomUp(root);
}
``````

It will take 0(n) time and O(nlogn) space , I am sure there is much better solution possible. answer Jan 15, 2014
+1 vote

I have used queue for Level order traversal and implemented it by using STL. "createBinaryTree" function will create a Binary tree until 0 is taken as the input that is, in my solution 0 can't be the input,we can change it according to our requirement. in function levelOrderTraversal, i have created a queue that will hold the current node and print it's data and then enqueue the right and left child of current node and dequeue the current node. for above tree, 1 is going to print first, then left and right child of 1 which is 2 and 3 is enqueued, now 2 is current node in the queue so 2 is going to be printed and child of 2 , 4 and 5 is enqueued and it continued in this way

``````#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std;

struct node{
int data;
struct node *left;
struct node *right;
};
struct node *root=NULL;
int count1=1;

struct node *createBinaryTree(struct node *root,int data){

if(root==NULL){
root=(struct node *) malloc(sizeof(struct node));
root->right=root->left=NULL;
root->data=data;
}
else{
if(count1%2!=0)
root->left=createBinaryTree(root->left,data);
else
root->right=createBinaryTree(root->right,data);
}
return root;
}

void levelOrderTraversal(struct node *root){
struct node *tmp;
if(root==NULL)
return;
queue <struct node *> myqueue; //creating a queue that will hold the address of nodes
myqueue.push(root);            //pushing the root of the tree
while(!myqueue.empty()){
tmp=myqueue.front();      // tmp will hold the address of the current node
cout <<' '<< tmp->data;
myqueue.pop();
if(tmp->left!=NULL)
myqueue.push(tmp->left);   //left address of current node is inserted in queue
if(tmp->right!=NULL)
myqueue.push(tmp->right);  //right address of current node is inserted in queue
}
}

int main(){
int data;
cin >> data;
while(data!=0){
root=createBinaryTree(root,data);
cin >>data;
}
levelOrderTraversal(root);
return 0;
}
``````

Time complexity is O(n) and space complexity is O(n). answer Jun 10, 2016
better explained @shashikant i have used the same method to solve level order traversal related questions.
Similar Questions
+4 votes

Given binary tree is:

``````            1
/     \
2        3
/  \        \
4   5         6
/   \
7     8
``````

The output will be 7,8,4,5,6,2,3,1

+3 votes

Given a binary tree print it in inward spiral order i.e first print level 1, then level n, then level 2, then n-1 and so on.

For Ex -

``````         1
2           3
4    5       6     7
8 9  10 11  12 13  14 15
``````

Print- 1 15 14 13 12 11 10 9 8 2 3 7 6 5 4