DSA Graph Valid Tree

The problem

Graph Valid Tree gives a graph on vertices 0 to n minus 1 and its edges. The question is whether the graph forms a single tree.

A tree connects every vertex and holds no cycle. Both halves matter. The answer is True only when the graph is connected and cycle-free.

cases = [
    (5, [[0, 1], [0, 2], [0, 3], [1, 4]], True),
    (4, [[0, 1], [1, 2], [2, 0], [0, 3]], False),
    (5, [[0, 1], [2, 3]], False),
    (4, [[0, 1], [1, 2], [2, 3]], True),
]
for n, edges, expected in cases:
    print("n", n, "edges", edges, "-> tree:", expected)

The second graph fails on a cycle. The third fails on connection, because vertex 4 stands alone and the pairs never join.

Intuition: count the edges

The first idea counts edges. A tree on n vertices holds exactly n minus 1 edges. The count looks like a complete test.

def count_check(n, edges):
    return len(edges) == n - 1

edges = [[0, 1], [1, 2], [2, 0]]
print("count check passes:", count_check(4, edges))
print("vertex 3 on any edge:", any(3 in e for e in edges))
print("true verdict: False")

The count passes a graph that is plainly not a tree. Its three edges close a triangle, and vertex 3 has no edge at all. A count can see neither flaw.

Brute force: flood from every vertex

The brute force checks both halves directly. The edge count must equal n minus 1. Then a flood from every vertex must reach all n vertices.

A flood is a walk that spreads along edges to every reachable vertex. A connected graph with exactly n minus 1 edges cannot hold a cycle, so the two checks together settle both halves.

def valid_brute(n, edges):
    if len(edges) != n - 1:
        return False, 0
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    visits = 0
    for start in range(n):
        seen = {start}
        stack = [start]
        while stack:
            node = stack.pop()
            visits += 1
            for nxt in graph[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)
        if len(seen) != n:
            return False, visits
    return True, visits

print("star graph:", valid_brute(5, [[0, 1], [0, 2], [0, 3], [1, 4]]))
print("split graph:", valid_brute(5, [[0, 1], [2, 3], [3, 4], [4, 2]]))

The star passes at the price of five floods. Every flood rewalks edges the earlier floods already crossed. That repetition is the cost the optimal method removes.

The optimal solution: union every edge, then count the roots

Union-find merges the ends of each edge, and one failed union means a cycle while more than one root at the end means the graph is split. That one sentence is the whole method.

A failed union is a union whose ends already share a root. Such an edge closes a loop. One root after all edges means one connected group.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def valid_tree(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return False, "cycle"
    roots = len({uf.find(i) for i in range(n)})
    if roots != 1:
        return False, "disconnected"
    return True, "tree"

cases = [
    (5, [[0, 1], [0, 2], [0, 3], [1, 4]], (True, "tree")),
    (4, [[0, 1], [1, 2], [2, 0], [0, 3]], (False, "cycle")),
    (5, [[0, 1], [2, 3]], (False, "disconnected")),
    (4, [[0, 1], [1, 2], [2, 3]], (True, "tree")),
]
for n, edges, expected in cases:
    result = valid_tree(n, edges)
    print("n", n, "->", result, "match:", result == expected)

All four cases pass, and each failure names its reason. The verdict and the reason come from the same single pass.

Walkthrough: the cycle graph, edge by edge

Four vertices start as four single groups. The first two edges merge groups. The third edge tells the real story.

parent = list(range(4))

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

edges = [[0, 1], [1, 2], [2, 0], [0, 3]]
for a, b in edges:
    ra, rb = find(a), find(b)
    if ra == rb:
        print("edge", [a, b], "- ends share root", ra, "-> cycle")
        break
    parent[rb] = ra
    groups = {}
    for v in range(4):
        groups.setdefault(find(v), []).append(v)
    print("edge", [a, b], "- groups:", sorted(groups.values()))

The third edge joins two vertices already inside one group, so the verdict is a cycle. The fourth edge never runs. The disconnected case ends differently, since its unions all succeed but several roots remain standing, and the root count gives that verdict.

Complexity

The brute force floods once per vertex, and each flood can visit every vertex, so its time is O(n squared). Union-find makes one pass over the edges, so its time grows with the edge count.

Both store one entry per vertex, plus the edge list. Their extra space is O(n).

def brute_visits(n, edges):
    graph = {i: [] for i in range(n)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)
    visits = 0
    for start in range(n):
        seen = {start}
        stack = [start]
        while stack:
            node = stack.pop()
            visits += 1
            for nxt in graph[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)
    return visits

def union_count(n, edges):
    parent = list(range(n))

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

    unions = 0
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[rb] = ra
            unions += 1
    return unions

for n in (5, 10, 20):
    edges = [[i, i + 1] for i in range(n - 1)]
    print("vertices", n, "- flood visits:", brute_visits(n, edges), " unions:", union_count(n, edges))

At 20 vertices the floods pay 400 visits against 19 unions. One pass replaces a flood per vertex.

Edge cases and pitfalls

A single vertex with no edges is a tree. It is connected by standing alone, and it holds no cycle.

A self-loop is a cycle of length one. Its union fails at once, because both ends are the same vertex.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

def valid_tree(n, edges):
    uf = UnionFind(n)
    for a, b in edges:
        if not uf.union(a, b):
            return False, "cycle"
    roots = len({uf.find(i) for i in range(n)})
    if roots != 1:
        return False, "disconnected"
    return True, "tree"

print("single vertex:", valid_tree(1, []))
print("self-loop:", valid_tree(1, [[0, 0]]))
print("two vertices, no edge:", valid_tree(2, []))
print("two vertices, one edge:", valid_tree(2, [[0, 1]]))
print("empty graph:", valid_tree(0, []))

The empty graph answers False. Zero vertices leave zero roots, and a tree needs exactly one root. The failed-union test and the root count must both run, because each one alone passes some graph that is not a tree.