# Challenge: Check if a Directed Graph is Tree or Not

Given a graph, can you write a code to check if it is a tree or not? A solution is placed in the "solution" section to help you, but we would suggest trying to solve it on your own first.

We'll cover the following

## Problem Statement

In this problem, you have to implement isTree() method to take a directed graph as an input and find out if it is a tree. Remember, a graph could only be a tree under the conditions stated below:

• Each node, except root, has exactly one parent
• There are no cycles
• 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.



### Method Prototype

boolean isTree(Graph g);


g is a directed graph represented by an adjacency list.

### Output

It returns true if the given graph is a tree, otherwise, the function returns false.

### Sample Input

graph = {
0 -> 1
0 -> 2
0 -> 3
3 -> 4
}


### Sample Output

True


### Explanation

A graph from the sample input is a tree because it doesnâ€™t contain any loop, and if we start from any vertex as a source we can reach all the remaining vertices of the graph.

An illustration is also provided for your understanding.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.