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