Graph Valid Tree

MediumUnion-Find (DSU)Blind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given n nodes labeled 0 to n - 1 and a list of undirected edges, where edges[i] = [a, b] connects nodes a and b. Return true if the edges make up a valid tree, and false otherwise. A valid tree links all n nodes with exactly one path between any two of them: every node must be reachable from every other node, and there must be no cycle. A single node with no edges counts as a tree.

Examples

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

Every node is reachable and nothing loops back.

Node 0 connects to 1, 2 and 3, and node 1 connects to 4, so all 5 nodes are linked. No edge closes a loop, so each pair of nodes has exactly one path between them.

n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] returns false

The highlighted edges close a loop through 1, 2 and 3.

Edges [1,2], [2,3] and [1,3] form a loop, so nodes 1 and 3 are joined by two different paths. That rules out a tree.

n = 4, edges = [[0,1],[2,3]] returns false

There's no loop, but nodes 0 and 1 can't reach nodes 2 and 3. A tree has to connect all 4 nodes, which takes 3 edges.

Constraints

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no self-loops or repeated edges.

Hints

Hint 1

Think about what makes a tree. How many edges do n connected nodes need, and what happens when you add one more?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

A graph on n nodes is a tree exactly when it has n - 1 edges and no cycle, since n - 1 edges without a cycle must connect everything. So reject any other edge count first. Then union the endpoints of each edge with union-find (path compression plus union by rank). If both endpoints already share a root, they were connected before this edge, so it closes a cycle. If every union succeeds, the edges merged all n nodes into one component.

Time

O(n * alpha(n))

Space

O(n)

Pitfall

Checking only for cycles accepts a forest like n = 4, edges = [[0,1],[2,3]], which has no loop but two separate pieces. You also need exactly n - 1 edges, or a final check that one component remains.

Solutions

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] parent = new int[n];
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] e : edges) {
            int ra = find(parent, e[0]);
            int rb = find(parent, e[1]);
            if (ra == rb) return false;
            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;
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }
}

from typing import List

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

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

        for a, b in edges:
            ra, rb = find(a), find(b)
            if ra == rb:
                return False
            if rank[ra] < rank[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            if rank[ra] == rank[rb]:
                rank[ra] += 1
        return True