#### Concepts Used

Depth First Search, Graph

#### Difficulty Level

Medium

#### Problem Statement :

Check whether the graph is a tree or not.

**See original problem statement here**

#### Solution Approach :

## Introduction :

For a graph to be tree, there should not be any loops and every vertex must be reachable from atleast one other vertex.

This problem can be solved by many ways like

Breadth First Search,Depth First SearchorDisjoint Set. Below we are going to go through some algorithms for beginners and discuss two of the above mentioned methods to solve this problem.

#### Method 1 :

The graph must follow these properties:

- If there are
`n`

vertices then there must be`n-1`

edges.- It should be connected i.e. every vertex can be reached with atleast one other vertex.
In trees, every node/vertex is connected to atleast one other vertex. Also the total number of edges is also

`n-1`

for`n`

nodes.

#### Method 2 :

The another way of checking our graph whether it is a tree or not that it should have following properties:

- It must not contain any cycle.
- It must be connected.
As, we can see this approach is almost similar to the approach in method

`1`

, our goal is to make sure that our graph has no loops or in other words it has exactly`n-1`

edges and must be connected. By this way we can ensure our graph is a tree, otherwise not. Refer to the example below for better understanding.See

C++implementation below.

#### Algorithms :

dfs():

- For each call, for some vertex
`v`

( dfs(`v`

) ), we will mark the vertex`v`

as visited (`visited[v]= true`

).- Iterate for all the adjacent vertices of
`v`

and for every adjacent vertex`a`

, do following :

- if
`a`

is not visited i.e`visited[a]= false`

,

and if`a`

has value`1`

.

recursively calldfs (.`a`

)

Complexity Analysis:The

time complexityof the first method is represented in the form of`O(V+E)`

, where`V`

is the number of verices and`E`

is the number of edges.The

space complexityof the algorithm is`O(V)`

for`visited[]`

array.

## Solutions:

[TABS_R id=1896]

[forminator_quiz id=”1928″]