# Solution: Graph Valid Tree

Let's solve the Graph Valid Tree problem.

## We'll cover the following

## Statement

Given an undirected `graph`

containing

A graph is a valid tree when all the nodes are connected and there is no cycle between them.

**Constraints:**

Let

$1 \leq$ $n$ $\leq 10^2$ $0 \leq$ $edges$ $\leq 5 \times 10^3$ There are no repeated edges

There are no self-loops

## Solution

To check if the graph is a valid tree, we start from the first node and move to adjacent nodes using a depth-first search. We mark visited nodes and look for cycles by checking if a node has been visited before. If we encounter a previously visited node that is not the parent, we have found a cycle, indicating the graph is not a tree. If the depth-first search started from the first node is complete, but some nodes remain unvisited, the graph is not connected, making it not a tree. If all nodes have been visited and no cycles are found, the graph is a valid tree.

The following are the steps of the algorithm:

Initialize a

`visited`

list to keep track of nodes that will be visited during the traversal of the graph.Starting from the first node, start traversing adjacent nodes in the graph.

While traversing the adjacent nodes in the graph, mark the current node as visited in the

`visited`

list.Pick an adjacent node and check if the node has been visited before.

If a node has not been visited before, continue the traversal from this node.

Otherwise, if the node has been visited before and is not the parent of the current node, a cycle has been found. Return FALSE.

After completing the depth-first search, traverse the

`visited`

list and check if the value of any index is FALSE; it means the graph is disconnected, return FALSE. Otherwise, if all values are TRUE, return TRUE, indicating the graph is a tree.

The following illustration demonstrates the algorithm:

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