Challenge: Check if a Given 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
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 connected to every other vertex through either a direct edge or a graph traversal.
You have to implement is_tree()
function which will take a graph as an 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
Take a look at the illustration below to understand better.
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.