Introduction
A Binary Search Tree (BST) is a tree in which the key of the nodes of the left sub-tree has a lower value than the key of its parent node, and the key of the right sub-tree is greater than or equal to the key of its parent node.
This blog will discuss the problem of finding the level of each node in a tree from the source node using BFS. We will discuss this article in detail. Let’s start going!

Problem Statement
In this problem, we are given a tree with v vertices, and we have to find the level of each node from the source node in a tree.
Let’s look at the problem of finding the level of each node in a tree from the source node using BFS with some examples.
Sample Examples
Example 1:
Input:

Output:
Level Nodes
0 --> 0
2 --> 1
1 --> 2
1 --> 3
1 --> 4
2 --> 5
2 --> 6
3 --> 7
Explanation:
A level of each node from the source node is determined using the Breadth First Search technique.
Example 2:
Input:

Output:
Level Nodes
0 --> 0
2 --> 1
1 --> 2
1 --> 3
2 --> 4
3 --> 5
2 --> 6
3 --> 7
4 --> 8
Explanation:
A level of each node from the source node is determined using the Breadth First Search technique.
Approach
We will discuss BFS (Breadth First Search) Technique to find the level of each node from the source node. It is a level order traversal method. It starts from the source nodes and traverses neighbor nodes and so on. It can be used to determine each node's level from a given source node.
Algorithm
✔️ Create the tree, a queue to hold the nodes, and place the root or first node in the queue.
✔️ Create an extra array nlevel of size v ( where n is the number of vertices) and a visited array.
✔️ Traverse a loop while the queue is not empty.
✔️ Make the current node as visited true.
✔️ Remove a node from the queue, insert its child nodes, and update the size of the inserted node as nlevel[child] = nlevel[node]+1.
✔️ Print the node along with its level.
Implementation
C++ Program to find the level of each node in a tree from the source node using BFS.
#include <bits/stdc++.h>
using namespace std;
void Levels_of_nodes(vector<int> graph[], int v, int z)
{
int nlevel[v];
bool vis[v];
queue<int> q;
q.push(z);
nlevel[z] = 0;
vis[z] = true;
// BFS traversal
while (!q.empty())
{
z = q.front();
q.pop();
for (int i = 0; i < graph[z].size(); i++)
{
int y = graph[z][i];
if (!vis[y])
{
q.push(y);
nlevel[y] = nlevel[z] + 1;
vis[y] = true;
}
}
}
// printing the level and nodes
cout << "Level"<< " "<< "Nodes" << endl;
for (int i = 0; i < v; i++)
cout << " " << nlevel[i] << " --> " << i << endl;
}
// Driver function
int main()
{
int v = 8;
vector<int> tree[v];
tree[0].push_back(2);
tree[0].push_back(3);
tree[0].push_back(4);
tree[2].push_back(1);
tree[3].push_back(5);
tree[3].push_back(6);
tree[6].push_back(7);
Levels_of_nodes(tree, v, 0);
return 0;
}
Output:
Level Nodes
0 --> 0
2 --> 1
1 --> 2
1 --> 3
1 --> 4
2 --> 5
2 --> 6
3 --> 7
Time Complexity
The time complexity of the above approach for the problem of finding the level of each node from the source node in a tree using BFS is O(n), as every node is visited only once.
Space Complexity
The space complexity of the above approach for the problem of finding the level of each node from the source node in a tree using BFS is O(n) as we are using extra space to store the node in the queue.
Check out this problem - Largest BST In Binary Tree
Check out this problem - Largest BST In Binary Tree