LeetCode 261: Graph Valid Tree — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Graph | DFS | Tree | Union Find

The Problem

Given n nodes and a list of undirected edges, determine if the edges form a valid tree. A valid tree must be connected and have exactly n-1 edges with no cycles.

Approach

First check if the number of edges equals n-1, which is a necessary condition for a tree. Build an adjacency list representation of the graph, then perform DFS from node 0 to detect cycles and check connectivity. The graph is a valid tree if no cycles are found during DFS and all nodes are visited.

Time: O(n + m) · Space: O(n + m)

Code

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n - 1:
            return False

        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        visited = set()

        def dfs(node, parent):
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor != parent:
                    if neighbor in visited or not dfs(neighbor, node):
                        return False
            return True

        # Check if the graph is connected
        if not dfs(0, -1):
            return False

        return len(visited) == n