## 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__