Number of nodes at a given level in a tree using Breadth-First Search

Breadth-first Search

The method is fed an unweighted graph and the id of the source vertex as input. The method does not care if the input graph is directed or undirected.

The procedure is analogous to a fire spreading over a graph: in the zeroth step, just the source is on fire. At each step, the fire burning at each vertex spreads to all of its neighbors. The method expands the breadth of the "ring of fire" by one unit in one iteration

Approach 

The goal is to start Breadth-First Search from the root node and keep track of the level value of each node along the way. The root node is on the first level. The level of the children nodes will equal the level of the parent node plus one. The queue used to process nodes during Breadth-First Search traversal maintains a pair of node.value and node.level for each node in the tree.

Algorithm 

1. Consider the following: a tree graph is provided, along with level 'L.'
2. During Breadth-First Search traversal, create a Breadth First Search queue that holds node value and node level as a pair.
3. Make a Hash Map that records the Number of nodes in each level.
4. After adding the root node and its level to the Breadth First Search queue, begin iterative Breadth-First Search traversal.
5. During each traversal cycle, select a node front and its level from the queue.
6. Mark the visited node as popped.
7. Increase the Number of nodes at that level by one.
8. Visit each unvisited neighbor of the popped node, and insert each node into the queue with its level. 
9. Return the total number of nodes at the specified level in the tree once the Breadth First Search traversal is completed.

Code

1️⃣ In Cpp

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


void edgeadded(vector <int> graph[], int u, int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}
// count nodes at a 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 the mapping between level->number of nodes
    unordered_map<int,int> um;
    
    // Breadth First Search queue
    // stores {node value, node level}
    queue <pair<int,int>> q;
    // root is at the first level
    int Lev = 1;
    // push root into the queue
    q.push({root,Lev});
    
    // Perform Breadth-First Search 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 the number of nodes at that level by 1
        um[front.second]++;
        
        // Visit all the neighbour 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 = 8;
    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)
    edgeadded(graph,e.first,e.second);
    
    // define level
    int Lev = 2;
    cout<<"Number of Nodes at the Second Level = "<<countNodes(root,graph,Lev,n)<<endl;
    
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

Number of Nodes at the Second Level = 3

You can also try this code with Online C++ Compiler

Run Code

2️⃣ In Java 

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;
        }
    }
    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
    {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    
    // count nodes at a 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 the mapping between level->number of nodes
        HashMap<Integer,Integer> um = new HashMap<>();
        
        // Breadth First Search queue
        // stores {node value, node level}
        Queue <pair> q = new LinkedList<>();
        // root is at the first level
        int Lev = 1;
        // push root into the queue
        q.add(new pair(root,Lev));
        
        // Perform Breadth-First Search traversal
        // Traverse each node and find their level in the tree
        while(!q.isEmpty())
        {
            pair front = q.poll();
            visited[front.first] = true;
            
    
            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();


            while(itr.hasNext())
            {
                int node = (Integer)itr.next();
                if(visited[node] == false)
                    q.add(new pair(node,front.second+1));
            }
        }
        


        return um.get(level);
    }
    
    public static void main (String[] args)
    {


        int n = 8;
        int root = 0;
 


        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 Lev = 2;
        System.out.println("Number of Nodes at the Second Level = "+countNodes(root,graph,Lev,n));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output:

Number of Nodes at the Second Level = 3

You can also try this code with Online Java Compiler

Run Code

Complexity

Time Complexity

T(n) = O(V+E)

• V here denotes the Number of nodes in the tree.
• E here denotes the Number of edges in the node.
• n here denotes the Number of test cases or chances taken 

Space Complexity

A(n) = O(V), For the Breadth First Search queue employed, 

• V here denotes the Number of nodes in the tree.
• n here denotes the Number of test cases or chances taken 

Although we utilized a queue and visited all of the nodes, the method executes in linear time. The algorithm's time complexity is linear. Because we utilized a queue to visit all of the nodes, the worst space complexity will be N, resulting in linear space complexity.

Frequently Asked Questions

What is a Tree?

A tree is a non-linear and hierarchical data structure made up of nodes connected by edges. A tree is an abstract data type (ADT) that follows a hierarchical data gathering structure.

What is Breadth First Search?

When a dead end occurs in any iteration, the Breadth First Search (BFS) method traverses a graph in a bread toward motion and utilizes a queue to remember to retrieve the next vertex to start a search.

What is the approach toward the Number of nodes at a given level in a tree using Breadth First Search?

The purpose is to start Breadth-First Search from the root node and maintain track of each node's level value along the way. The first level contains the root node. The level of the children nodes will be one higher than the level of the parent node. For each node in the tree, the queue used to process nodes during Breadth-First Search traversal keeps a pair of node.value and node.level.

What is the Time Complexity of the Number of nodes at a given level in a tree using Breadth First Search?

Time Complexity for the above is T(n) = O(V+E)

V here denotes the Number of nodes in the tree, E here denotes the Number of edges in the node, n here denotes the Number of test cases or chances taken.

What is the Space Complexity of the Number of nodes at a given level in a tree using Breadth First Search? 

Space Complexity for the above is A(n) = O(V)

V here denotes the Number of nodes in the tree, n here denotes the Number of test cases or chances taken.

Also Read - Strong number in c

Conclusion

In this article, we understood the concept of the Number of nodes at a given level in a tree using BFS. 

After reading about BFS, are you not feeling excited to read/explore more articles on the topic of Ruby? Don't worry; Coding Ninjas has you covered. To learn, see Multithreading in Python, Descriptors in Python, and BorderLayout in Java.

Recommended Problems:

• Detect cycle in an undirected graph
• Burn Tree
• Size of largest BST in a Binary Tree.
• Partial BST.
   

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! 

Do upvote our blogs if you find them helpful and engaging!