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:

How to create a random string in C++?

Leave a Reply

Your email address will not be published. Required fields are marked *