Level Order Traversal of Binary Tree in C++

Here we are going to write a program to implement level order traversal of binary tree in c++. This level order traversal is also known as breadth first search traversal or BFS traversal. In this traversal for each node, first the node is visited and put in a FIFO i.e., in a queue, then the node is popped out and its child nodes are put in the queue then again they are popped out and this process repeats till the queue becomes empty.

Level Order Traversal Approach-

• First create a queue and push root into it.

• Run while loop till queue is not empty (while(!q.empty()))

• Initialize temp = q.front() and print temp data

• Pop first element from queue

• Push temp's left and right data if they exists

Here we are considering -1 as NULL.

Level Order Traversal of Binary Tree in C++

#include <bits/stdc++.h>
using namespace std;

class node
{
public:
    int data;
    node *left;
    node *right;

    node(int val)
    {
        data = val;
        left = NULL;
        right = NULL;
    }
};

node *buildTree(node *root)
{
    int data;
    cout << "Enter data: " << endl;
    cin >> data;
    root = new node(data);

    if (data == -1)
    {
        return NULL;
    }

    cout<< "Enter data to insert in left of " << data << endl;
    root->left = buildTree(root->left);

    cout << "Enter data to insert in right " << data << endl;
    root->right = buildTree(root->right);

    return root;
}

void levelorder(node *root)
{
    queue<node *> q;
    q.push(root);
	
    
    while (!q.empty())
    {
        node *temp = q.front();
        cout << temp->data << " ";
        q.pop();
       
        if (temp->left)
        {
            q.push(temp->left);
        }
        if (temp->right)
        {
         	q.push(temp->right);
        }
        
    }
}

int main()
{
    node *root = NULL;

    // creating tree
    root = buildTree(root);
    levelorder(root);
}

Output

Enter data: 
5
Enter data to insert in left of 5
Enter data: 
3
Enter data to insert in left of 3
Enter data: 
1
Enter data to insert in left of 1
Enter data: 
-1
Enter data to insert in right 1
Enter data:
-1
Enter data to insert in right 3
Enter data:
4
Enter data to insert in left of 4
Enter data:
-1
Enter data to insert in right 4
Enter data:
-1
Enter data to insert in right 5
Enter data:
8
Enter data to insert in left of 8
Enter data:
6
Enter data to insert in left of 6
Enter data:
-1
Enter data to insert in right 6
Enter data:
-1
Enter data to insert in right 8
Enter data:
9
Enter data to insert in left of 9
Enter data:
-1
Enter data to insert in right 9
Enter data:
-1
5 3 8 1 2 6 9

If you want to see the output in new line then we need to modify this code. Here's the modified code.

Code to print levels in new line

#include <bits/stdc++.h>
using namespace std;

class node
{
public:
    int data;
    node *left;
    node *right;

    node(int val)
    {
        data = val;
        left = NULL;
        right = NULL;
    }
};

node *buildTree(node *root)
{
    int data;
    cout << "Enter data: " << endl;
    cin >> data;
    root = new node(data);

    if (data == -1)
    {
        return NULL;
    }

    cout<< "Enter data to insert in left of " << data << endl;
    root->left = buildTree(root->left);

    cout << "Enter data to insert in right " << data << endl;
    root->right = buildTree(root->right);

    return root;
}

void levelorder(node *root)
{
    queue<node *> q;
    q.push(root);
    q.push(NULL);

    while (!q.empty())
    {
        node *temp = q.front();
        q.pop();

        if (temp == NULL)
        {
            cout << endl;
            if (!q.empty())
            {
                q.push(NULL);
            }
        }
        else
        {
            cout << temp->data << " ";
            
            if (temp->left)
            {
                q.push(temp->left);
            }
            if (temp->right)
            {
                q.push(temp->right);
            }
        }
    }
}

int main()
{
    node *root = NULL;

    // creating tree
    root = buildTree(root);
    levelorder(root);
}

Output

Enter data: 
5
Enter data to insert in left of 5
Enter data: 
3
Enter data to insert in left of 3
Enter data: 
1
Enter data to insert in left of 1
Enter data: 
-1
Enter data to insert in right 1
Enter data:
-1
Enter data to insert in right 3
Enter data:
4
Enter data to insert in left of 4
Enter data:
-1
Enter data to insert in right 4
Enter data:
-1
Enter data to insert in right 5
Enter data:
8
Enter data to insert in left of 8
Enter data:
6
Enter data to insert in left of 6
Enter data:
-1
Enter data to insert in right 6
Enter data:
-1
Enter data to insert in right 8
Enter data:
9
Enter data to insert in left of 9
Enter data:
-1
Enter data to insert in right 9
Enter data:
-1

5
3 8 
1 2 6 9