Limited Period Offer : 20% Discount on online/offline courses, for more details call/whatsapp

Level Order Traversal in Binary Tree

1 min read
1 year ago By Aniket Prajapati

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.

Jul 10, 2023 10:06 Back to Articles

Other Articles

How to use and upload profile photos to AWS s3 using laravel jetstream

Using jetsream to upload photos to s3 configuration and details

1 year ago By Santosh Kshirsagar
Binary Search top interview questrions.

As we know binary search itself is a imp topic to be learned in Data Structures and Algorithm so, This article contains all the important questions that can be asked in coding interview or online assessment(OA) . Here the questions clear all the concepts and the variety in questions helps to understands the logic behind the concepts .

1 year ago By Aniket Prajapati
10 common JavaScript interview questions that you might encounter !!!

In this article, we will discuss 10 JS questions that are commonly asked in interviews. These questions cover a range of JavaScript topics and are commonly asked in interviews to assess a candidate's understanding of the language. Make sure to practice and understand these concepts to perform well in JavaScript interviews.

1 year ago By Mitali Gupta
What is Agile Development ? What is Agile Development ?

Agile development is a software development approach that emphasizes flexibility, collaboration, and continuous delivery. It involves iterative development, continuous feedback, a collaborative approach, adaptability, and continuous improvement.

2 years ago By Mitali Gupta