Graph Valid Tree

Difficulty: Medium Source: NeetCode

Problem

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

A valid tree must be: connected (all nodes reachable from any node) and acyclic (no cycles).

Example 1: Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true

Example 2: Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false

Constraints:

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= ai, bi < n
• No self-loops or repeated edges

Prerequisites

Before attempting this problem, you should be comfortable with:

• Tree properties — a tree with n nodes has exactly n-1 edges and is connected
• Union-Find — for cycle detection in undirected graphs
• DFS / BFS — for checking connectivity

1. DFS (Check Connected + Acyclic)

Intuition

A valid tree with n nodes has exactly n-1 edges (necessary but not sufficient alone — you also need connectivity). So first check len(edges) == n - 1. If that passes, just check connectivity: run DFS from node 0 and verify all nodes are reachable. If both conditions hold, it’s a valid tree.

Why does n-1 edges + connectivity imply no cycles? Because a connected graph with n nodes and n-1 edges is always a tree.

Algorithm

1. If len(edges) != n - 1, return False.
2. Build adjacency list for the undirected graph.
3. Run DFS from node 0, tracking visited nodes.
4. Return True if all n nodes were visited.

Solution

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

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

    visited = set()

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(0)
    return len(visited) == n


print(validTree(5, [[0,1],[0,2],[0,3],[1,4]]))         # True
print(validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]))   # False (cycle)
print(validTree(1, []))                                 # True (single node)
print(validTree(2, []))                                 # False (disconnected)

Complexity

• Time: O(V + E)
• Space: O(V + E) for graph and visited set

2. Union-Find (Cycle Detection)

Intuition

Union-Find is a natural fit for undirected cycle detection. For each edge (a, b): if a and b are already in the same component, adding this edge would create a cycle — return False. Otherwise, merge their components. After processing all edges, check that we ended up with exactly one component (connectivity check).

Algorithm

1. Initialize Union-Find with n nodes.
2. For each edge (a, b):
   • If find(a) == find(b), cycle detected — return False.
   • Otherwise, union(a, b).
3. Return True if all edges processed successfully (and len(edges) == n-1 ensures connectivity).

Solution

def validTree(n: int, edges: list[list[int]]) -> bool:
    parent = list(range(n))
    rank = [0] * n

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False  # cycle!
        # Union by rank
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    for a, b in edges:
        if not union(a, b):
            return False

    # Check connectivity: exactly one component
    roots = {find(i) for i in range(n)}
    return len(roots) == 1


print(validTree(5, [[0,1],[0,2],[0,3],[1,4]]))         # True
print(validTree(5, [[0,1],[1,2],[2,3],[1,3],[1,4]]))   # False
print(validTree(1, []))                                 # True
print(validTree(3, [[0,1]]))                            # False (disconnected)

Complexity

• Time: O(E * α(N)) — nearly O(E) with path compression and union by rank
• Space: O(N) for parent and rank arrays

Common Pitfalls

Necessary vs sufficient conditions. Having n-1 edges alone doesn’t guarantee a tree (could be disconnected + have a cycle). Connectivity alone doesn’t guarantee a tree (could have cycles). You need both. The cleanest check: n-1 edges + connected = tree.

Undirected DFS: tracking parent. In standard DFS cycle detection for undirected graphs, you need to track the parent node to avoid incorrectly flagging the edge you came from as a “back edge”. However, the n-1 edges shortcut avoids this entirely.

Union-Find: checking one component. After Union-Find, make sure all nodes belong to a single component. The len(edges) == n-1 check is equivalent but checking roots explicitly handles edge cases like n=1, edges=[] more clearly.