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:

1. The naive one (finding the height of the tree and traversing each level and printing the nodes of that level).
2. 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.