Count the number of nodes at given level in a tree using BFS

Difficulty Level Easy
Frequently asked in Alation BankBazaar JP Morgan Square Taxi4Sure
Breadth First Search Graph Tree Tree TraversalViews 2696

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.

Count the number of nodes at given level in a tree using BFS

Number of nodes at 2nd level = 3

Explanation

Count the number of nodes at given level in a tree using BFS

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

  1. Consider, a tree graph is given along with level ‘L’.
  2. Create the BFS queue that stores node value & node level as a pair during BFS traversal.
  3. Create a Hash Map that stores number of nodes present in each level.
  4. Begin iterative BFS traversal after adding the root node along with it’s level into the BFS queue.
  5. During each iteration of the traversal, pop a node front & it’s level from the queue.
  6. Mark the popped node as visited.
  7. Increase the number of nodes at that particular level by 1.
  8. 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].
  9. After the BFS traversal is over, return the total number of nodes at the given level in the tree.

Count the number of nodes at given level in a tree using BFS

 

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

  1. Time Complexity: T(n) = O(V+E)
  2. 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

Translate »