Graph Valid Tree

Traversal checks — count, connect, detect

A tree needs exactly n - 1 edges, so reject any other count first. Then build an adjacency list, a list of each node's neighbors, and walk from node 0.

This is the graph cycle detection pattern: remember the parent you arrived from. Seeing that parent again is just the same undirected edge; seeing any other visited neighbor exposes a cycle. The walk must also visit all n nodes.

def valid_tree(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)
 
    seen = {0}
    stack = [(0, -1)]
    while stack:
        node, parent = stack.pop()
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if neighbor in seen:
                return False
            seen.add(neighbor)
            stack.append((neighbor, node))
 
    return len(seen) == n

Time O(V + E), space O(V + E) — the walk touches each node and edge once, while the adjacency list stores both directions of every edge.

Union-find — reject a closed loop while merging

Union-find, also called disjoint-set union, tracks which nodes already belong to the same connected group. Each edge asks for the roots of its endpoints:

• Different roots merge, reducing the number of groups by one.
• Equal roots mean a path already connects the endpoints, so this edge closes a cycle.

def valid_tree(n: int, edges: list[list[int]]) -> bool:
    parent = list(range(n))
    size = [1] * n
    components = n
 
    def find(node: int) -> int:
        while node != parent[node]:
            parent[node] = parent[parent[node]]
            node = parent[node]
        return node
 
    for a, b in edges:
        root_a = find(a)
        root_b = find(b)
        if root_a == root_b:
            return False
 
        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a
        size[root_a] += size[root_b]
        components -= 1
 
    return components == 1

Path compression shortens future root searches, while union by size keeps trees shallow. The inverse Ackermann function α(V) grows so slowly that it behaves like a tiny constant at any practical input size.

Time O(V + E·α(V)), space O(V) for the parent and size arrays.

The useful union-find instinct is crisp: an undirected edge whose endpoints already share a root is exactly the edge that closes a cycle.