#### Level Order Traversal

** It is a technique used to traverse a tree by starting from root to traversing all nodes of one level before moving to other level.**

###### How does Level Order Traversal works ?

The main idea of level order traversal is to traverse all the nodes of a lower level before moving to any of the nodes of a higher level. This can be done in any of the following ways:

- The naive one (finding the height of the tree and traversing each level and printing the nodes of that level).
- Using queue.

###### Level Order Traversal Using Queue:

We need to visit the nodes in a lower level before any node in a higher level, this idea is quite similar to that of a queue. Push the nodes of a lower level in the queue. When any node is visited, pop that node from the queue and push the child of that node in the queue.

```
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int d)
{
this->data=d;
this->left=NULL;
this->right=NULL;
}
};
node* buildtree(node* root)
{
int data;
cout<<"enter val"<<endl ;
cin>>data;
root=new node(data);
if(data ==-1)
{
return NULL;
}
cout<<"left of"<<data<<endl;
root->left=buildtree(root->left);
cout<<"right of"<<data<<endl;
root->right=buildtree(root->right);
return root;
}
void leftOrderTraversal(node* root)
{
queue<node*> q;
q.push(root);
q.push(NULL);
while(!q.empty())
{
node* temp;
temp=q.front();
q.pop();
if(temp!=NULL)
{
cout<<temp->data<<" ";
if(temp->left)
{
q.push(temp->left);
}
if(temp->right)
{
q.push(temp->right);
}
}
else {
cout<<endl;
if(!q.empty())
{
q.push(NULL); // to seperate elements of queue levelwise
}
}
}
}
int main(){
node* root=NULL;
//creating tree;
root=buildtree(root);
leftOrderTraversal(root);
return 0 ;
}
```

Time Complexity : O(N). Space Complexity : O(N). where, N nodes present in a binary tree.