Graph Valid Tree — Cycle and Connectivity Check

Problem Statement#

LeetCode 261 — Graph Valid Tree (Medium)

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [a, b] indicates that there is an undirected edge between nodes a and b in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Constraints:

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2, 0 <= a, b smaller than n, a != b
• No duplicate edges, no self-loops.

Example 1:

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true

Example 2:

n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false (cycle through 1-2-3-1)

Why This Problem Matters#

Graph Valid Tree is a tier-one interview classic at Google, Amazon, and Meta because it forces you to articulate the precise mathematical definition of a tree. Many candidates cite "no cycles" alone and miss the connectivity requirement. The problem also showcases the elegance of Union Find: a 10-line solution that runs in near-linear time and feels almost magical.

A tree on n nodes has two equivalent characterizations:

1. Connected and acyclic.
2. Connected with exactly n - 1 edges.

Either characterization yields a one-pass O(N + E) algorithm. The Union Find variant additionally generalizes to dynamic connectivity problems (LC 305 — Number of Islands II, LC 1319 — Network Connections), which is why interviewers love it.

The Core Insight#

There are two ways to verify a graph is a tree:

• Edge count plus connectivity. If len(edges) != n - 1, return false immediately. Otherwise check the graph is connected via BFS or DFS from node 0; if all n nodes are reachable, it is a tree.
• Union Find. Process each edge with union(a, b). If at any point find(a) == find(b), the edge would create a cycle, so return false. After processing all edges, verify the number of distinct roots is one (or that you performed exactly n - 1 successful unions).

The first approach is faster to write but has two phases. The Union Find approach is denser but also faster in practice for large graphs because it interleaves cycle detection with connectivity checking.

The edge-count optimization is a powerful early-out. With n nodes, a tree has exactly n - 1 edges. More than that creates a cycle; fewer leaves a node disconnected. One arithmetic check eliminates many bad inputs in O(1).

Visual Dry Run#

n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]. Run Union Find:

parent = [0, 1, 2, 3, 4]   (each node is its own root)
 
Edge [0, 1]: find(0)=0, find(1)=1, different. Union.
parent = [0, 0, 2, 3, 4]
 
Edge [1, 2]: find(1)=0, find(2)=2, different. Union.
parent = [0, 0, 0, 3, 4]
 
Edge [2, 3]: find(2)=0, find(3)=3, different. Union.
parent = [0, 0, 0, 0, 4]
 
Edge [1, 3]: find(1)=0, find(3)=0, SAME ROOT.
Cycle detected -> return false.

For Example 1 with [[0,1],[0,2],[0,3],[1,4]], every union connects new components, four successful unions on n - 1 = 4 edges, and the final structure is one connected component with no cycle. Return true.

Solution (Optimal)#

Python (Edge count plus BFS connectivity)#

from collections import deque, defaultdict
 
class Solution:
    def validTree(self, n: int, edges: list[list[int]]) -> bool:
        # A tree on n nodes has exactly n - 1 edges (necessary condition)
        if len(edges) != n - 1:
            return False
 
        adj = defaultdict(list)
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)                    # undirected graph
 
        visited = {0}
        queue = deque([0])
 
        # Standard BFS reachability from node 0
        while queue:
            node = queue.popleft()
            for nxt in adj[node]:
                if nxt not in visited:
                    visited.add(nxt)
                    queue.append(nxt)
 
        # If we reached every node, the graph is connected.
        # Combined with the n-1 edge check, it must also be acyclic.
        return len(visited) == n

JavaScript (Union Find)#

/**
 * Union Find with path compression and union by rank.
 * Detects cycle the moment two endpoints share a root.
 */
var validTree = function(n, edges) {
    if (edges.length !== n - 1) return false;             // structural sanity check
 
    const parent = Array.from({length: n}, (_, i) => i);
    const rank = new Array(n).fill(0);
 
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];                // path compression
            x = parent[x];
        }
        return x;
    };
 
    const union = (a, b) => {
        const ra = find(a), rb = find(b);
        if (ra === rb) return false;                      // cycle detected
        if (rank[ra] < rank[rb]) parent[ra] = rb;
        else if (rank[ra] > rank[rb]) parent[rb] = ra;
        else { parent[rb] = ra; rank[ra]++; }
        return true;
    };
 
    for (const [a, b] of edges) {
        if (!union(a, b)) return false;                   // would create a cycle
    }
    return true;                                          // n-1 edges + no cycles = tree
};

Complexity. Both run in O(N + E) time. Union Find with path compression and union by rank is technically O((N + E) alpha(N)) where alpha is essentially constant. Space is O(N) for parent / rank or visited / adjacency structures.

Common Mistakes#

1. Skipping the edge-count check. Without edges.length == n - 1, you must run two separate checks (cycle + connectivity). The edge count is a single comparison that simplifies the algorithm dramatically.
2. Treating the graph as directed. Edges are undirected. Add both a -> b and b -> a in the adjacency list.
3. Detecting cycles with a visited array (BFS only). A naive BFS visits every node once but the simple visited check misses cycles unless you also track the parent. The cleanest fix is Union Find or the edge-count shortcut.
4. Returning true on disconnected forests. A forest with no cycles still fails the tree test if it has multiple components. Make sure your algorithm catches that.
5. Off-by-one with n - 1. Some candidates check len(edges) smaller than n or <= n - 1. The required condition is exactly n - 1.

Interview Tips#

• State the tree definition first. "A graph is a tree iff it is connected and acyclic, equivalently n - 1 edges and one component." This earns immediate trust.
• Use the edge-count shortcut. It is a one-liner and instantly demonstrates mathematical maturity.
• Mention Union Find. Even if you implement BFS, explicitly say "Union Find is also natural here and runs in near-linear time." Interviewers love the awareness.
• Trace Example 2. Walk through the cycle detection on [[0,1],[1,2],[2,3],[1,3],[1,4]] to show your code handles cycles cleanly.

Follow-up Questions#

1. Edges streaming online. Use Union Find. Each new edge either joins two components or forms a cycle.
2. Weighted edges, return MST instead. Switch to Kruskal algorithm — sort edges by weight and Union Find them.
3. Detect cycle in a directed graph. Use three-color DFS or Kahn topological sort instead of Union Find.
4. Find the longest path in the tree once it is valid. Run BFS from any node to find a leaf u, then BFS from u to find the farthest node v. Path u to v is the diameter.
5. Count the number of trees in a forest. Run Union Find and count distinct roots at the end.

Key Takeaways#

• A graph is a valid tree iff it is connected and acyclic, equivalently has exactly n - 1 edges and one component.
• The edge-count shortcut (len(edges) == n - 1) reduces the problem to a single connectivity check.
• Union Find detects cycle and connectivity in one pass — interviewers love this approach.
• BFS or DFS connectivity from node 0 plus the edge count works equally well.
• Both implementations run in O(N + E) time, optimal for the problem.
• The pattern generalizes to LC 305, LC 547, and LC 1319 with minimal modification.