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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment