Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
2.
Understanding the Problem
2.1.
Trees
2.2.
Forest
3.
Example
3.1.
Input
3.2.
Expected Output
3.3.
Algorithm
3.4.
Code
3.4.1.
C++
3.4.2.
Output
3.5.
Time Complexity
4.
4.1.
How do you count tree nodes?
4.2.
How can we determine the number of ordered trees?
4.3.
What data structures do we use to represent graphs?
4.4.
Give an example where a graph is used.
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count the Number of Trees in a Forest

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Data Structure and Algorithm problems are some of the most complex, exciting, and skill-boosting exercises that you, as a fellow coder can perform. In this article, we will go over one such problem, counting the number of trees in a forest.

So before going ahead, letâ€™s first understand the problem at hand.

Understanding the Problem

The problem statement that we have here is;

Given the vertices of a forest, Find the number of trees in that forest.

Now we need to understand the terminologies used in this problem

Trees

In Graph Theory, an undirected graph has any two vertices connected by exactly one path or an equivalent connected acyclic undirected graph.

Below is a graphical example of a tree.

Forest

As the name suggests, a forest is nothing more than a collection of trees. More specifically, A forest is also an undirected graph having any two vertices connected by exactly one path, an equivalent connected acyclic undirected graph, or a disjoint union of trees.

Below is a graphical representation of a forest.

To learn more about Graphs, their types, and terminologies, check out the article on graphs here.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Now that you have a grasp of the problem statement, we will implement the solution using an example.

Letâ€™s look at the graphical representation of the forest that we will use to count the number of trees.

Input

``edges = { { 1,2 }, {6,7}, {6,5}, {2,3}, {2,4}, {8,7} }``

Expected Output

To understand the expected output, we can see a graphical representation.

From the image above, we can derive an expected output

The number of trees in the given forest are: 3

Algorithm

Here we will use an approach known as Depth First Search Algorithm recursively. In this approach, we increment the count if every connected node is marked visited from one source, meaning a tree is formed.

Letâ€™s see the algorithm step by step:

1. For every Node that you have in your forest, Apply DFS Algorithm. If you are not familiar with DFS, check out Depth First Search(DFS) before moving forward.
2. If every node that is connected is visited once then increment the count.
3. If some nodes are not visited, then again perform DFS Transversal. If you want to know ore about DFS Transversal, check out DFS Traversal and DFS Traversal of a Graph to know gain insights.
4. The count that you will obtain after following these steps will be the number of trees in your forest.

Code

Using the above algorithm, you can write the code for this problem in several programming languages of your choice using their respective syntaxes. Let's look at a code example.

C++

``````#include<bits/stdc++.h>
using namespace std;
void insert(vector<int> vec[], int parent, int child){
vec[parent].push_back(child);
vec[child].push_back(parent);
}
void recurred(int temp, vector<int> vec[], vector<bool> &check){
check[temp] = true;
int size = vec[temp].size();
for(int i = 0; i < size; i++){
if (check[vec[temp][i]] == false){
recurred(vec[temp][i], vec, check);
}
}
}
int Trees_in_Forest(vector<int> vec[], int vertice){
int count = 0;
vector<bool> check(vertice, false);
for(int i = 0; i < vertice; i++){
if(check[i] == false){
recurred(i, vec, check);
count++;
}
}
return count;
}
int main(){
int vertice = 9;
vector<int> vec[vertice];
insert(vec, 1, 2);
insert(vec, 6, 7);
insert(vec, 6, 5);
insert(vec, 2, 3);
insert(vec, 2, 4);
insert(vec, 8, 7);
cout<<"The Number of Trees in the Forest are: "<<Trees_Forest(vec, vertice);
return 0;
}``````

Time Complexity

The time complexity for an algorithm is the amount of time it takes to process an input of some length. The time complexity for the given code is O(V+E), where 'V' represents the number of vertices present in the graph and 'E' is the number of edges present in the graph.
Check out this problem - Largest BST In Binary Tree

How do you count tree nodes?

To count the tree nodes, you can determine the left and the right height of the given Tree for the current root value and if it is equal, then return the value of (2height â€“ 1) as the count of nodes.

How can we determine the number of ordered trees?

For a binary tree, we can Choose (2n,n)/(n+1) (Catalan number) as the answer for the number of ordered trees, as mcdowella said.

What data structures do we use to represent graphs?

We represent graphs by edges and vertices, so we can use either a list Adjacency List or a matrix Adjacency Matrix to store the input for a graph.

Give an example where a graph is used.

To allocate a resource operating system, uses Resource Allocation Graph.

Also Read - Strong number in c

Conclusion

With that, we will conclude our article. In this article, we have covered the problem, "Count the Number of Trees in a Forest", some terminologies related to the problem, and graphs. Check out other ds & graph problems such as finding all the mother vertices of the graphbreadth-first searchdepth-first search, and more. Also, look at significant graph algorithms like Dijkstra's AlgorithmBellman Ford Algorithm, and Floyd Warshall Algorithm. Wait, we have got more than just graphs. Wanna learn more about web technologies? Why not have a look at web technologies on Coding Ninjas Studio? Practice data structures and algorithmsinterview questionsDBMScomputer networks, and operating systems to crack the interviews of big tech giants. Explore other fields like machine learningdeep learningcomputer vision, and big data. Also, check out Interview Experiences for different companies.

Happy Learning!

Live masterclass