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).