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,
- Go to the next line
- 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
