Challenge: Check if a Directed Graph is Tree or Not

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.