Graph Valid Tree

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.

Approach

A valid tree must have exactly n - 1 edges and be acyclic. Use Union-Find to detect cycles while connecting edges. If any union finds two nodes already connected, a cycle exists. With n - 1 edges and no cycle, the graph is connected.

Why It Works

In an undirected graph, being a tree is equivalent to being connected and acyclic. Union-Find detects cycles, and the n - 1 edge check plus no cycles guarantees connectivity. Therefore the graph is a valid tree iff these conditions hold.

Complexity

• Time: O(n + e)
• Space: O(n)

Reference Implementation (Python)

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

        parent = list(range(n))
        rank = [0] * n

        def find(x: int) -> int:
            while x != parent[x]:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(a: int, b: int) -> bool:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            if rank[ra] < rank[rb]:
                parent[ra] = rb
            elif rank[ra] > rank[rb]:
                parent[rb] = ra
            else:
                parent[rb] = ra
                rank[ra] += 1
            return True

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