Table of Contents
Description
The problem “Count the number of nodes at given level in a tree using BFS” states that you are given a Tree (acyclic graph) and a root node, find out number of nodes at L-th level.
Acyclic Graph: It is a network of nodes connected through edges which has no closed loop.
Note: The root node itself is at 1st level in the tree.
Example
Consider the tree given below, rooted at node 0.
Number of nodes at 2nd level = 3
Explanation
Breadth First Search
Approach
The idea is to perform BFS starting from root node and keep track of level value of each node along the path. The root node is at 1st level. The level of children nodes will be level of parent node + 1. The queue use to process nodes during BFS traversal stores {node.value , node.level} as pair for every node in the tree.
Algorithm
- Consider, a tree graph is given along with level ‘L’.
- Create the BFS queue that stores node value & node level as a pair during BFS traversal.
- Create a Hash Map that stores number of nodes present in each level.
- Begin iterative BFS traversal after adding the root node along with it’s level into the BFS queue.
- During each iteration of the traversal, pop a node front & it’s level from the queue.
- Mark the popped node as visited.
- Increase the number of nodes at that particular level by 1.
- Visit each not visited neighbors of the node popped, Insert each node into queue along with it’s level [i.e. (level of front) + 1].
- After the BFS traversal is over, return the total number of nodes at the given level in the tree.
Code
C++ program to Count the number of nodes at given level in a tree using BFS
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// function to add undirected edge between two nodes
void addEdge(vector <int> graph[], int u, int v)
{
graph[u].push_back(v);
graph[v].push_back(u);
}
// count nodes at particular level in the tree
int countNodes(int root, vector <int> graph[], int level, int n)
{
// mark all the nodes unvisited
vector <bool> visited(n,false);
// to store mapping between level->number of nodes
unordered_map<int,int> um;
// BFS queue
// stores {node value, node level}
queue <pair<int,int>> q;
// root is at first level
int L = 1;
// push root into queue
q.push({root,L});
// Perform BFS traversal
// Traverse each node and find their level in the tree
while(!q.empty())
{
auto front = q.front();
q.pop();
visited[front.first] = true;
// Increase number of nodes at that level by 1
um[front.second]++;
// Visit all the neighbor nodes of the popped node
for(auto node : graph[front.first])
{
if(!visited[node])
q.push({node,front.second+1});
}
}
// return number of nodes at 'level'
return um[level];
}
int main()
{
// define number of nodes & root node
int n = 7;
int root = 0;
// construct the graph & link the nodes by edges
vector <int> graph[n];
vector <pair<int,int>> edges = {{0,1},{0,2},{0,3},{1,4},{1,5},{4,6}};
for(auto e : edges)
addEdge(graph,e.first,e.second);
// define level
int L = 2;
cout<<"Number of Nodes at 2nd Level = "<<countNodes(root,graph,L,n)<<endl;
return 0;
}Number of Nodes at 2nd Level = 3
Java Program to Count the number of nodes at given level in a tree using BFS
import java.util.*;
import java.io.*;
class TutorialCup
{
// class definition to handle pairs
static class pair
{
int first,second;
pair(int u,int v)
{
first = u;
second = v;
}
}
// function to add undirected edge between two nodes
static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
{
graph.get(u).add(v);
graph.get(v).add(u);
}
// count nodes at particular level in the tree
static int countNodes(int root, ArrayList<ArrayList<Integer>> graph, int level, int n)
{
// mark all the nodes unvisited
boolean [] visited = new boolean[n];
// to store mapping between level->number of nodes
HashMap<Integer,Integer> um = new HashMap<>();
// BFS queue
// stores {node value, node level}
Queue <pair> q = new LinkedList<>();
// root is at first level
int L = 1;
// push root into queue
q.add(new pair(root,L));
// Perform BFS traversal
// Traverse each node and find their level in the tree
while(!q.isEmpty())
{
pair front = q.poll();
visited[front.first] = true;
// Increase number of nodes at that level by 1
if(um.containsKey(front.second))
um.put(front.second, um.get(front.second)+1);
else
um.put(front.second, 1);
Iterator itr = graph.get(front.first).iterator();
// Visit all the neighbor nodes of the popped node
while(itr.hasNext())
{
int node = (Integer)itr.next();
if(visited[node] == false)
q.add(new pair(node,front.second+1));
}
}
// return number of nodes at 'level'
return um.get(level);
}
public static void main (String[] args)
{
// define number of nodes & root node
int n = 7;
int root = 0;
// construct the graph & link the nodes by edges
ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<n;i++)
graph.add(new ArrayList<Integer>());
int [][] edges = {{0,1},{0,2},{0,3},{1,4},{1,5},{4,6}};
for(int i=0; i<edges.length; i++)
addEdge(graph,edges[i][0],edges[i][1]);
// define level
int L = 2;
System.out.println("Number of Nodes at 2nd Level = "+countNodes(root,graph,L,n));
}
}Number of Nodes at 2nd Level = 3
Complexity Analysis
- Time Complexity: T(n) = O(V+E)
- Space Complexity: A(n) = O(V), for the BFS queue used.
The algorithm runs in linear time as we have used a queue and traversed over all the nodes. The algorithm has linear time complexity. As we have used a queue to traverse over all the nodes, the worst space complexity will be N, thus linear space complexity.
V = number of nodes in the tree
E = number of edges in the node