Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
LeetCode 261

Graph Valid Tree

MediumJul 9, 2026graphdfsconnected-componentscycle-detectionunion-find

A tree is just a connected graph with exactly `n - 1` edges, so the edge count is checked first as a fast fail — it catches both 'too few edges to reach everything' and 'an extra edge means a cycle somewhere' — before a single stack DFS from node `0` confirms the rest is actually connected.

The problem

Implement `validTree(n, edges)` for `n` nodes labelled `0` to `n - 1` and a list of undirected edges. Return whether the edges form a valid tree — every node connected, with no cycles.

`n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]` is a valid tree (`true`). `n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]` has a cycle (`1`-`2`-`3`-`1`), so it's `false`.

The approach

A tree on `n` nodes has exactly `n - 1` edges — no more, no fewer. That single arithmetic check does double duty: fewer edges can't possibly reach every node, and any extra edge beyond `n - 1` has to close a cycle somewhere. It's a fast fail before any traversal runs.

Once the edge count passes, the only remaining question is connectivity: build the same array-indexed adjacency list as `countComponents`, then run one stack DFS from node `0` and check whether `visited` ends up covering all `n` nodes.

Correctness relies on the two checks together, not either alone — `edges.length === n - 1` by itself doesn't rule out a disconnected graph that happens to have a cycle elsewhere, and a connectivity check alone doesn't rule out an extra edge creating a cycle. Combined, they pin down exactly one shape: a connected acyclic graph.

The solution

js
class Solution {
    /**
     * @param {number} n
     * @param {number[][]} edges
     * @returns {boolean}
     */
    validTree(n, edges) {
        if (edges.length !== n - 1) return false;

        const graph = Array.from({ length: n }, () => []);
        for (const [e1, e2] of edges) {
            graph[e1].push(e2);
            graph[e2].push(e1);
        }

        const visited = new Set();
        visited.add(0);
        const stack = [0];
        while (stack.length) {
            const node = stack.pop();
            for (const neighbour of graph[node]) {
                if (!visited.has(neighbour)) {
                    visited.add(neighbour);
                    stack.push(neighbour);
                }
            }
        }

        return visited.size === n;
    }
}

Time O(V + E)Space O(V)

All entries