Graph Valid Tree - Leetcode Solution

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:

1. Create a visited set to keep track of nodes we have already visited.
2. Create an adjacency list to represent the graph.
3. Initialize a queue or stack (depending on whether we use BFS or DFS) with the starting node.
4. 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.
5. 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.

1