Level Order Traversal

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:

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

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

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

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

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

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.

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.

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

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

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

In the end we get the result as below:

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: