Graph Valid Tree

Graph Valid Tree asks a deceptively simple question — is this pile of nodes and edges actually a tree? It is a perfect showcase for Union-Find, the data structure that answers "are these two things already connected?" in almost constant time.

The slow way first

You could build an adjacency list and run a DFS or BFS, tracking visited nodes and watching for an edge back to an already-visited node (a cycle), then separately confirm every node was reached (connected). That works and is O(n + e), but it takes a fair amount of bookkeeping — a visited set, a parent to skip, and a final connectivity count.

The cleaner observation: a tree has a precise shape. On n nodes it has exactly n − 1 edges, and it has no cycle. If both are true, connectivity comes for free.

The idea: count the edges, then union them

First a quick filter: if there are not exactly n − 1 edges, it cannot be a tree — return false immediately. Then process each edge with Union-Find: every node starts in its own group, and each edge tries to union its two endpoints. If an edge ever connects two nodes that are already in the same group, that edge closes a cycle — not a tree.

Why does the count check let us skip a connectivity check? With exactly n − 1 edges and no cycle, the graph must be one connected piece — there is no way to leave any node out without either dropping below n − 1 edges or forming a cycle somewhere else.

Walk through it

Step through the animation. The parent array starts as [0,1,2,3,4] — each node is its own group. We union the four edges one by one; each time the two endpoints have different roots, so no cycle. At the end, the demo shows that edge (3,4) would find the same root for both — that is exactly the cycle signal we watch for.

Pseudocode

if number of edges != n - 1:
    return False                     # wrong count, cannot be a tree
 
parent[i] = i  for every node i      # each node in its own group
 
find(x): follow parent pointers up to the root of x's group
 
for each edge (u, v):
    ru, rv = find(u), find(v)
    if ru == rv:
        return False                 # u and v already connected -> cycle
    parent[rv] = ru                  # union the two groups
 
return True                          # n-1 edges and no cycle -> valid tree

The Python solution

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return False
        parent[rv] = ru
    return True

• The early len(edges) != n - 1 check rejects any graph with the wrong edge count before we do any work.
• parent = list(range(n)) puts every node in its own group: parent[i] = i.
• find(x) walks parent pointers up until it reaches a node that is its own parent — the root of that group.
• For each edge, if find(u) == find(v) the two endpoints are already connected, so this edge closes a cycle — return false.
• Otherwise parent[rv] = ru merges the groups. Survive all edges and the count check, and it is a valid tree.

Complexity

The α(n) is the inverse Ackermann function — so small it is effectively constant. The parent array is the only extra storage, giving O(n) space.

When this pattern shows up

Practice