Graph Valid Tree 🔒

Problem

You have n nodes labeled 0 to n - 1 and a list of undirected edges, each [u, v]. Return True if these edges form a valid tree, and False otherwise.

A graph is a tree exactly when it is connected (every node reachable from every other) and acyclic (no cycles). Equivalently, a tree on n nodes has exactly n - 1 edges and is connected — or, has n - 1 edges and no cycle. Either pair of conditions is sufficient.

Examples

• n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] → True — 4 edges = 5 − 1, connected, no cycle. It’s a tree.
• n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] → False — 5 edges on 5 nodes; the extra edge [1,3] closes a cycle 1–2–3–1.
• n = 4, edges = [[0,1],[2,3]] → False — only 2 edges; the graph splits into two disconnected pieces.
• n = 1, edges = [] → True — a single node with no edges is a valid (trivial) tree.

Constraints

• 1 <= n <= 2000
• 0 <= len(edges) <= 5000
• No self-loops and no duplicate edges in the input.

Think about it first

TL;DR

A tree = exactly n − 1 edges and connected. Check the count, then verify connectivity with DFS/BFS, or detect any cycle with union-find — all O(V + E).

Approach 1 — Brute force (count edges, then DFS for connectivity)

The naive-but-correct intuition: a tree on n nodes must have exactly n − 1 edges. With that count fixed, “no cycle” and “connected” become the same condition, so a single connectivity check settles it. Reject early if the count is wrong.

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

        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        seen = set()

        def dfs(node: int) -> None:
            seen.add(node)
            for nei in adj[node]:
                if nei not in seen:
                    dfs(nei)

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

Complexity: O(V + E) time and space. There’s nothing to “kill” here — this is efficient; it’s labeled brute force only because it leans on the edge-count shortcut rather than reasoning about cycles directly.

Approach 2 — BFS connectivity check

The insight: same n − 1 edge shortcut, but confirm connectivity with an iterative BFS from node 0. Preferred over recursive DFS when the tree could be a long chain (up to 2000 deep) that would risk Python’s recursion limit; DFS is a touch shorter to write.

from collections import deque


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

        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        seen = {0}
        queue = deque([0])
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                if nei not in seen:
                    seen.add(nei)
                    queue.append(nei)

        return len(seen) == n

Walkthrough (n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]):

• len(edges) = 4 = 5 − 1 ✓. Adjacency: 0:[1,2,3], 1:[0,4], 2:[0], 3:[0], 4:[1].
• BFS from 0 visits 0, then 1,2,3, then 4. seen = {0,1,2,3,4}, size 5 = n → True.
• On [[0,1],[2,3]] (n=4): only 2 edges ≠ 3, rejected instantly → False.

Complexity: O(V + E) time, O(V + E) space.

Approach 3 — Union-find (cycle detection while building)

The insight: process edges one at a time, keeping disjoint sets of connected nodes. For edge [u, v], if u and v are already in the same set, adding this edge would close a cycle → not a tree. Otherwise union them. After all edges, a single remaining component means connected. Union-find (disjoint-set union with path compression + union by rank) makes each operation near-constant. This version needs no separate edge-count check — it catches both failure modes directly.

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

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

        for u, v in edges:
            ru, rv = find(u), find(v)
            if ru == rv:
                return False                     # edge closes a cycle
            if rank[ru] < rank[rv]:
                ru, rv = rv, ru
            parent[rv] = ru
            if rank[ru] == rank[rv]:
                rank[ru] += 1
            components -= 1

        return components == 1

Walkthrough (n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]):

• Union 0-1, 1-2, 2-3 — all merge, components drops 5→4→3→2.
• Edge [1,3]: find(1) and find(3) already share a root (0/1/2/3 are one set) → cycle → return False.

Complexity: O(E · α(V)) time (α = inverse Ackermann, effectively constant), O(V) space. No adjacency list needed.

Common pitfalls

• Skipping the connectivity check after seeing n − 1 edges — a graph can have n − 1 edges yet be a cycle plus an isolated node (disconnected). The count alone is not sufficient; you need count and connectivity (or the union-find cycle check).
• Treating the undirected graph as directed: add both u→v and v→u to the adjacency list.
• In a plain-DFS cycle check (without the edge-count trick) you must skip the edge back to your parent, or every undirected edge looks like a 2-cycle. The union-find and count+connectivity approaches sidestep this entirely.
• Forgetting the n = 1, edges = [] base case — 0 edges = 1 − 1, one node reached, valid tree.

Pattern takeaway

“Is this graph a tree?” reduces to two independent facts — exactly n − 1 edges and connected — and any two of {n−1 edges, connected, acyclic} imply the third. Verify connectivity with one traversal, or let union-find detect the cycle as you add edges. Union-find is the natural tool whenever “would adding this edge merge two already-joined nodes?” is the question.