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)

A tree on n nodes has exactly n − 1 edges. Once the count is fixed, “no cycle” and “connected” become the same condition, so a single connectivity check settles it. Reject early if the count is wrong.

def validTree(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. It is labeled brute force only because it leans on the edge-count shortcut rather than reasoning about cycles directly; the traversal itself is optimal.

Approach 2 — BFS connectivity check

Same n − 1 edge shortcut, but confirm connectivity with an iterative BFS from node 0. Prefer this over recursive DFS when the tree could be a long chain (up to 2000 deep), which risks hitting Python’s recursion limit; DFS is slightly shorter to write.

from collections import deque


def validTree(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, so the count passes. 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 immediately → False.

This example is the tree below, rooted at node 0:

graph TD
    0 --- 1
    0 --- 2
    0 --- 3
    1 --- 4

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

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

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 the graph is 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.

def validTree(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.