Challenge 7: Check if an Undirected Graph is Tree or Not

In this lesson, you will learn the difference between a graph and a tree. You will use this knowledge for the challenge below.

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 bool isTree(Graph g) function, which will take a graph as input and it will find out if it is a tree.

Input

This is an undirected graph.

Output

It 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.