Challenge: Check if an Undirected Graph is Tree or not
In this lesson, we will learn the difference between a graph and a tree. You will use this knowledge for the challenge below.
We'll cover the following
Problem Statement #
The next section will tackle the tree data structure. For now, here’s the basic difference between a graph and a tree. A graph can only be a tree under two conditions:
- There are no cycles.
- The graph is connected.
A graph is connected when there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices. Each vertex must be able to reach every other vertex through either a direct edge or through a graph traversal.
You have to implement isTree()
function which will take a graph as input and find out if it is a tree.
Input #
An undirected graph.
Output #
Returns True
if the given graph is a tree. Otherwise, it returns False
.
Sample Input #
graph = {
0 - 1
0 - 2
0 - 3
3 - 4
}
Sample Output #
true
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.