Graph Valid Tree

PracticeNeetCode ↗LeetCode ↗

Given n nodes labeled 0 to n - 1 and a list of undirected edges, determine whether these edges form a valid tree — fully connected, with no cycles.

Example

Key Pointers

• A valid tree with n nodes must have exactly n - 1 edges — more implies a cycle, fewer means it can't possibly be connected. Check this first as a cheap early exit.
• Beyond the edge count, the graph must also be fully connected — a single traversal from any node should reach all n nodes.
• Since edges are undirected, track the parent node during DFS to avoid immediately backtracking along the edge just traversed.

Step-by-Step Analysis

1. If the number of edges isn't exactly n - 1, return False immediately.
2. Build an adjacency list from the edges.
3. DFS from node 0, tracking visited nodes and the parent to avoid re-traversing the edge just arrived from.
4. Return True only if all n nodes were visited — the edge-count check already ruled out cycles, so full visitation confirms connectivity.

Complexity

Time: O(V + E) — Space: O(V + E)

Code

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

    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    visited = set()

    def dfs(node: int, parent: int) -> None:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor != parent and neighbor not in visited:
                dfs(neighbor, node)

    dfs(0, -1)
    return len(visited) == n

Code Explanation

How the solution above works, piece by piece.

1. A tree on n nodes has exactly n - 1 edges. Any other count → False immediately.
2. Build an undirected adjacency list (each edge in both directions).
3. DFS from node 0, skipping the node we came from and any node already visited. The not in visited check was missing from the original code on this page, which made it recurse forever when node 0 is on a cycle (e.g. n = 4, edges 0–1, 1–2, 2–0); it's fixed above.
4. With exactly n − 1 edges, "connected" and "no cycle" mean the same thing, so it's enough to check that the DFS reached all n nodes.
5. O(V + E) time and space.

Visual Walkthrough

Running it on n = 5, edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]:

Video Explanation

NeetCode — LeetCode 261