## Similar Problems

Similar Problems not available

# Graph Valid Tree - Leetcode Solution

## Companies:

LeetCode: Graph Valid Tree Leetcode Solution

Difficulty: Medium

Topics: breadth-first-search union-find depth-first-search graph

The Graph Valid Tree problem on LeetCode asks whether a given graph is a valid tree. A graph is a valid tree if it is undirected, connected, and has no cycles.

To solve this problem, we can use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the graph and check if it meets the conditions of a valid tree.

Algorithm:

- Create a visited set to keep track of nodes we have already visited.
- Create an adjacency list to represent the graph.
- Initialize a queue or stack (depending on whether we use BFS or DFS) with the starting node.
- While the queue or stack is not empty, do the following: a. Pop the next node from the queue or stack. b. If the node is already in the visited set, return False, because we have found a cycle. c. Otherwise, add the node to the visited set and add its neighbors to the queue or stack.
- After traversing the entire graph, if all nodes have been visited and there are no cycles, return True. Otherwise, return False.

Code Implementation:

Using DFS:

```
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
# create visited set and adjacency list
visited = set()
adj_list = {i: [] for i in range(n)}
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)
def dfs(node, parent):
# if the node is already visited, return False
if node in visited:
return False
# add node to visited set and explore its neighbors
visited.add(node)
for neighbor in adj_list[node]:
# skip parent of current node to avoid cycle
if neighbor == parent:
continue
# if neighbor has cycle, return False
if not dfs(neighbor, node):
return False
return True
# start the DFS traversal from the first node
return dfs(0, -1) and len(visited) == n
```

The time complexity of this DFS solution is O(V+E) where V is the number of vertices and E is the number of edges.

Using BFS:

```
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
# create visited set, adjacency list, and initial queue
visited = set()
adj_list = {i: [] for i in range(n)}
queue = collections.deque([0])
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)
# BFS traversal
while queue:
node = queue.popleft()
if node in visited:
return False
visited.add(node)
for neighbor in adj_list[node]:
queue.append(neighbor)
# remove the edge between node and neighbor
adj_list[neighbor].remove(node)
return len(visited) == n
```

The time complexity of this BFS solution is also O(V+E) where V is the number of vertices and E is the number of edges.

## Graph Valid Tree Solution Code

`1`