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

Livewire contenteditable to variable using entagle

using livewire apline js to update variable in livewire component

1 year ago By Santosh Kshirsagar
Introducing ECMAScript 6 (ES6): A New Era for JavaScript Development Introducing ECMAScript 6 (ES6): A New Era for JavaScript Development

In this article, we'll explore the important changes and improvements that came with ECMAScript 6 (ES6), and how they've made JavaScript programming better.

1 year ago By Mitali Gupta
How to connect aws RDS instance using mysql workbench

Learn to connect RDS instance(mysql/mariadb) using mysql workbech.

2 years ago By Santosh Kshirsagar
Best Websites for Building Resumes

In this article, we will explore five top websites that can assist you in crafting a compelling resume to increase your chances of getting shortlisted by companies.

2 years ago By Mitali Gupta