# Number of Nodes at given level in a tree using BFS (Graph) in C++

In this tutorial, we will learn. How to count the **number of nodes at a given level in a tree using BFS in C++**. At a particular level, there can be a different amount of nodes. We are going to learn how to implement it in C++.

## Introduction to tree using graph

Binary Tree contains nodes and edges between them. In a Binary tree, there can be a maximum of two children for each parent. Nodes are the data storing blocks. And edges are used for connecting the nodes.

Level in a tree is the distance from the top node to that node including the top node.

In this problem, we have to find the number of nodes a given particular level. The tree we are going to create is made using an undirected graph.

We are going to use BFS short form for breadth-first search. In this technique, we will first traverse the whole level then move on to the next one.

To determine the level of a node we increment the level of its parent and set it to the child.

6 / \ --> 3 8 level 2 has 2 elements. / \ / \ 1 4 7 9

## Program to get the number of nodes at given level in a tree in C++

#include <iostream> #include <list> using namespace std; class Graph { int V; list<int>* adj; public: Graph(int V); void addEdge(int v, int w); int BFS(int s, int l); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); } int Graph::BFS(int s, int l) { bool* visited = new bool[V]; int level[V]; for (int j = 0; j < V; i++) { visited[j] = false; level[j] = 0; } list<int> queue; visited[s] = true; queue.push_back(s); level[s] = 0; while (!queue.empty()) { s = queue.front(); queue.pop_front(); for (auto i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { level[*i] = level[s] + 1; visited[*i] = true; queue.push_back(*i); } } } int count = 0; for (int j = 0; j < V; i++) if (level[j] == l) count++; return count; } int main() { int n,level,data,level1; cout<<"Enter the number of nodes"; cin>>n; Graph g(n); for(int i=0;i<n;i++){ cin>>level>>data; g.addEdge(level,data); } cout<<"Enter the level"; cin>>level1 cout << g.BFS(0, level1); return 0; }

#### Input and Output

Enter the number of node 4 0 1 1 2 1 3 2 5 Enter the level 2 1

In the above code Firstly we enter the elements with there levels. Secondly, we enter the required level check. We can perform this program without the help of graphs also.

** Conclusion**

The above problem of Nodes at a given level in a tree using BFS (Graph) in C++. This solution can also be used for many more problem which contains levels.

**Also Checkout:**

## Leave a Reply