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.

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.


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



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.