261. Graph Valid Tree

Most graph problems ask you to explore. This one asks you to classify: does a pile of edges form a tree or not? The whole solution turns on remembering two small facts about trees, and once you have them, union-find reads the answer off in one pass.

The problem

You get n nodes labeled 0..n-1 and a list of undirected edges. Decide whether those edges form a valid tree — one connected piece with no cycles. (Full statement on LeetCode.)

A quick original example: with n = 4 and edges [[0,1],[1,2],[2,3]] you get a straight chain, which is a tree, so the answer is true. Add [3,0] and you’ve closed a loop — now it’s false.

Intuition: two conditions, and why one number does half the work

A graph on n nodes is a tree exactly when it is connected and acyclic. Those two properties are tightly linked by the edge count. A tree always has precisely $n-1$ edges:

$\text{edges} = n - 1$

That single equality is a cheap filter that catches half the failures before you touch the graph. Too many edges (more than $n-1$) guarantees a cycle. Too few guarantees at least two disconnected pieces. So if the count is wrong, you can reject immediately.

The elegant part is what happens once the count is right. If you have exactly $n-1$ edges and no edge ever joins two nodes that were already connected, then every edge merged two separate groups. Starting from n isolated nodes and doing $n-1$ successful merges collapses everything into a single group — connected and acyclic at once. So the only thing left to check is whether any edge tries to link two nodes already in the same group. That’s a textbook union-find (disjoint set) question.

Solution

Filter on the edge count, then union each edge. If both endpoints already share a root, this edge would close a cycle, so bail out.

class Solution {
    public boolean validTree(int n, int[][] edges) {
        // A tree on n nodes has exactly n-1 edges:
        // more -> a cycle, fewer -> disconnected. Reject either up front.
        if (edges.length != n - 1) return false;

        int[] parent = new int[n];
        int[] size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }  // each node its own group

        for (int[] edge : edges) {
            int rootA = find(parent, edge[0]);
            int rootB = find(parent, edge[1]);
            if (rootA == rootB) return false;        // ends already joined -> cycle
            if (size[rootA] < size[rootB]) {         // union by size: hang the
                int tmp = rootA; rootA = rootB; rootB = tmp;  // smaller tree under the larger
            }
            parent[rootB] = rootA;                   // union the two groups
            size[rootA] += size[rootB];
        }
        // n-1 successful unions from n groups leaves exactly one -> connected.
        return true;
    }

    private int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];           // path halving keeps trees flat
            x = parent[x];
        }
        return x;
    }
}

The edges.length != n - 1 guard is doing real work: because it guarantees exactly $n-1$ unions, “no cycle found” is enough to conclude the graph is connected. Drop that line and you’d have to run a separate connectivity check (a DFS from node 0, confirming every node got visited).

Complexity

	Time	Space
Union-find	$O(n \cdot \alpha(n))$	$O(n)$

Union by size plus path compression is what earns that bound: with both, each find is nearly constant — $\alpha(n)$ is the inverse Ackermann function, under 5 for any input you’ll ever see — so the pass is effectively linear. (Path compression alone, without balancing by size, degrades to $O(\log n)$ per operation.) The space is the two length-n arrays, parent and size.

In an interview

Say the two facts out loud before writing anything: “a tree is connected and acyclic, and that forces exactly $n-1$ edges.” Leading with the edge-count check signals you understand the structure, not just an algorithm. The trap is stopping there — n-1 edges alone doesn’t prove a tree. Picture four nodes with a triangle among 0,1,2 plus a stranded node 3: that’s three edges (n-1), yet it has a cycle and a disconnected vertex. That’s exactly why the union step still has to reject any edge that closes a loop.

If the interviewer prefers traversal over union-find, the DFS variant is equivalent: after the edge-count guard, DFS from node 0 and return true only if every node was reached. Both are $O(n)$ in spirit.

This is the same disjoint-set machinery behind Number of Connected Components — that problem just counts the groups instead of demanding exactly one. The cycle-detection angle also links it to Course Schedule, where a cycle means the prerequisites can’t be satisfied. More cousins live in the graph patterns hub.

References

• LeetCode 261 — Graph Valid Tree