ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Level Order Traversal

prodevelopertutorial March 30, 2020

In this tutorial we shall see how to print level by level of the tree nodes.

 

Problem Statement:

Given the root node of the tree, print the nodes level by level.

 

For example:

Consider the tree below:

 

Level Order Traversal

 

Here the level order traversal will be as below:

[a]

[b, c]

[d, e, f, g]

 

i.e we need to print the nodes level by level.

 

 

Level order traversal can also be written as below:

a, b, c, d, e, f, g

 

i.e without printing level by level, but by printing in single line.

 

We can solve this problem with help of queues.

 

Basic Idea:

 

Step 1: Enqueue the node

Step 2: Dequeue the node and print

Step 3: Enqueue left and right child of the node.

 

Now let’s apply these steps and check our result.

 

First enqueue the root node

Level Order Traversal

 

Now move the node “a” to output, mark it as visited. Insert left and right child of node “a”.

Level Order Traversal

 

Now select node ”b” move it to output. Then insert it’s children in queue.

Level Order Traversal

 

Now select node “c” move it to output. Insert it’s left and right children in to the queue.

Level Order Traversal

Similarly, if we do the same operation, we get our result.

 

Level Order Traversal

 

Now let’s see how to print level by level:

 

We follow below steps:

 

Step 1: Enqueue root

Step 2: Enqueue Null

Step 3: dequeue node and null

Step 4: Enqueue left and right child

Step 5: If the element is null then,

  1. Go to the next line
  2. Enqueue null.

 

Now let’s see the above steps by taking an example:

 

Initially we insert root node “a” and null.

Level Order Traversal

 

Now, dequeue a into the output vector.

 

Insert it’s left and right child as shown, mark it as visited.

Note that till now we are in the first line.

Level Order Traversal

 

Now, dequeue NULL, so when we dequeue null, we go to the next line and also insert NULL in to the array.

 

Level Order Traversal

 

Now in the next 2 iterations, we print b, insert its children d, e and print c, and insert it’s children f, g.

Level Order Traversal

 

Now we reach NULL, we go to the next line and insert NULL into the queue.

 

Level Order Traversal

 

In the end we get the result as below:

Level Order Traversal

 

Solution in C++

#include <iostream>
#include <queue>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


void display_level_order(Node *root) 
{ 
    // Base Case 
    if (root == NULL)  
        return; 
  
    queue<Node *> q; 
  
    // Enqueue Root and initialize height 
    q.push(root); 
  
    while (q.empty() == false) 
    { 
        // display front of queue and remove it from queue 
        Node *node = q.front(); 
        cout << node->data << " "; 
        q.pop(); 
  
        // Enqueue left child 
        if (node->left != NULL) 
            q.push(node->left); 
  
        // Enqueue right child 
        if (node->right != NULL) 
            q.push(node->right); 
    } 
} 

int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    int level = 2;

    cout<<"Solution = " <<endl;
    display_level_order(root); 

    return 0;  
}

 

Output:

Solution =
16 10 25 7 15 18 30

 

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2020 ProDeveloperTutorial.com
Get top courses from: Educative.io