Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is Depth First Search?
3.2.
What is Graph data structure?
3.3.
What is B-tree?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find the level of each node in a tree from the source node using BFS

Author Ayush Mishra
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

Binary Search Tree (BST) is a tree in which the key of the nodes of the left sub-tree has a lower value than the key of its parent node, and the key of the right sub-tree is greater than or equal to the key of its parent node.

This blog will discuss the problem of finding the level of each node in a tree from the source node using BFS. We will discuss this article in detail. Let’s start going!

Find the level of each node in a tree from the source node using BFS

Problem Statement

In this problem, we are given a tree with v vertices, and we have to find the level of each node from the source node in a tree.

Let’s look at the problem of finding the level of each node in a tree from the source node using BFS with some examples.

Sample Examples

Example 1:

Input:

Example1

Output: 

Level Nodes
 0 --> 0
 2 --> 1
 1 --> 2
 1 --> 3
 1 --> 4
 2 --> 5
 2 --> 6
 3 --> 7

 

Explanation: 

A level of each node from the source node is determined using the Breadth First Search technique.

 

Example 2:

Input:

Example2

Output: 

Level Nodes
 0 --> 0
 2 --> 1
 1 --> 2
 1 --> 3
 2 --> 4
 3 --> 5
 2 --> 6
 3 --> 7
 4 --> 8

 

Explanation: 

A level of each node from the source node is determined using the Breadth First Search technique.

Approach

We will discuss BFS (Breadth First Search) Technique to find the level of each node from the source node. It is a level order traversal method. It starts from the source nodes and traverses neighbor nodes and so on. It can be used to determine each node's level from a given source node.

Algorithm

✔️ Create the tree, a queue to hold the nodes, and place the root or first node in the queue.

✔️ Create an extra array nlevel of size v ( where n is the number of vertices) and a visited array.

✔️ Traverse a loop while the queue is not empty.

✔️ Make the current node as visited true.

✔️ Remove a node from the queue, insert its child nodes, and update the size of the inserted node as nlevel[child] = nlevel[node]+1.

✔️ Print the node along with its level.

Implementation

C++ Program to find the level of each node in a tree from the source node using BFS.

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


void Levels_of_nodes(vector<int> graph[], int v, int z)
{
  int nlevel[v];
  bool vis[v];
  queue<int> q;
  q.push(z);

  nlevel[z] = 0;

  vis[z] = true;
  
 // BFS traversal


  while (!q.empty()) 
  	{
     	z = q.front();
     	q.pop();
     
    	for (int i = 0; i < graph[z].size(); i++)
    		{
      			int y = graph[z][i];

      			if (!vis[y]) 
      				{
      					q.push(y);
     					nlevel[y] = nlevel[z] + 1;
      					vis[y] = true;
     				 }
    		}
  	 }


  // printing the level and nodes
  cout << "Level"<< " "<< "Nodes" << endl;
  for (int i = 0; i < v; i++)
   cout << " " << nlevel[i] << " --> " << i << endl;
}

// Driver function
int main()
{
  int v = 8;
  vector<int> tree[v];
 

   tree[0].push_back(2);
   tree[0].push_back(3);
   tree[0].push_back(4);
   tree[2].push_back(1);
   tree[3].push_back(5);
   tree[3].push_back(6);
   tree[6].push_back(7);
   
   Levels_of_nodes(tree, v, 0);
   return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output: 

Level Nodes
 0 --> 0
 2 --> 1
 1 --> 2
 1 --> 3
 1 --> 4
 2 --> 5
 2 --> 6
 3 --> 7
You can also try this code with Online C++ Compiler
Run Code

Time Complexity

The time complexity of the above approach for the problem of finding the level of each node from the source node in a tree using BFS is O(n), as every node is visited only once.

Space Complexity

The space complexity of the above approach for the problem of finding the level of each node from the source node in a tree using BFS is O(n) as we are using extra space to store the node in the queue.
Check out this problem - Largest BST In Binary Tree
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is Depth First Search?

Depth-first search is a tree or graph traversal technique. Backtracking is used for traversal in this case. This traversal visits the deepest node first, then returns to its parent node if that node has no siblings.

What is Graph data structure?

A graph is a data structure made up of vertices and edges. Vertices are also known as nodes, and edges are lines or arcs that connect any two nodes in the graph.

What is B-tree?

A B-tree is a self-balancing search tree in which each node can have multiple keys and more than two children. It is a broader version of the binary search tree.

Conclusion

Congratulations on finishing the blog! We have finished reading the problem of finding the level of each node in a tree from the source node using BFS. 

We hope this blog has helped you enhance your knowledge regarding the topic of Tree data structure, and if you want to learn more, then you can check articles on:-

1. Introduction to  Binary Search Tree

2. Sum and the Product of minimum and maximum elements of a Binary Search Tree

3. Breadth First Search (BFS).

4. Traversal in Binary Trees.

Please refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!

Happy learning!

Live masterclass