Graph Valid Tree

MediumUnion-Find · Graph Connectivity🧩 Union-Find LeetCode #261 ↗Updated Oct 30, 2026

Problem

You get n nodes labelled 0..n-1 and a list of undirected edges. Decide whether these edges form a single valid tree: every node is reachable from every other node and there is no cycle.

Inputn = 4, edges = [[0,1],[1,2],[1,3]]Outputtrue

Inputn = 4, edges = [[0,1],[1,2],[2,0]]Outputfalse (cycle, node 3 isolated)

Inputn = 3, edges = [[0,1]]Outputfalse (node 2 unreachable)

1 ≤ n ≤ 2000 · 0 ≤ edges.length ≤ 5000 · no self-loops or repeated edges

Try it yourself

Java

class Solution {
    public boolean validTree(int n, int[][] edges) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A graph on n nodes is a tree iff it has exactly n-1 edges and is connected (equivalently: n-1 edges and acyclic). So check the edge count first, then either confirm one component or that no edge closes a cycle.

PatternUnion-Find

Instinct Items get grouped by "connected", "same as" or "shares a" links and you keep asking which group something is in: merge sets with Union-Find.

Memory hack Find your boss, merge the bosses; squash the chain (path compression) and hang the short tree under the tall one (rank).

Open the Union-Find guide →

Approaches

Brute ForceReachability Check Before Each Edge

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

Add edges one by one. Before adding (u, v), BFS over the edges added so far: if v is already reachable from u, this edge closes a cycle. If no edge does, the graph is a forest, and a forest with exactly n-1 edges is a single tree.

Java

public boolean validTree(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        if (reachable(adj, e[0], e[1], n)) return false; // edge would close a cycle
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    return edges.length == n - 1; // acyclic + n-1 edges => connected
}

private boolean reachable(List<List<Integer>> adj, int src, int dst, int n) {
    boolean[] seen = new boolean[n];
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(src);
    seen[src] = true;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        if (u == dst) return true;
        for (int v : adj.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                queue.add(v);
            }
        }
    }
    return false;
}

Correct, but re-explores the graph for every edge.

BetterEdge Count + One Traversal

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

Reject immediately unless there are exactly n-1 edges. Then a single BFS/DFS from node 0 decides everything: if it reaches all n nodes the graph is connected, and connected with n-1 edges means no cycle is possible.

Java

public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    boolean[] seen = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    seen[0] = true;
    int visited = 1;
    while (!stack.isEmpty()) {
        int u = stack.pop();
        for (int v : adj.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                visited++;
                stack.push(v);
            }
        }
    }
    return visited == n;
}

Linear and simple, but must build an adjacency list first.

OptimalEdge Count + Union-Find

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

With exactly n-1 edges, the graph is a tree iff no edge joins two nodes that are already in the same set. Union-find answers “same set?” in near-constant time while streaming the edges, with no adjacency list.

Java

public boolean validTree(int n, int[][] edges) {
    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;
    }
    for (int[] e : edges) {
        int a = find(parent, e[0]), b = find(parent, e[1]);
        if (a == b) return false; // already connected -> cycle
        if (size[a] < size[b]) { int t = a; a = b; b = t; }
        parent[b] = a; // union by size
        size[a] += size[b];
    }
    return true;
}

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

Only an int array of size n, early exit on the first cycle edge.

Pro tip

The edge-count check is what lets you skip the connectivity test — say why: n-1 edges with no cycle cannot leave two components.

At a glance

Level	Approach	Time	Space
Brute Force	Reachability Check Before Each Edge	`O(E·(V + E))`	`O(V + E)`
Better	Edge Count + One Traversal	`O(V + E)`	`O(V + E)`
Optimal	Edge Count + Union-Find	`O(V + E·α(V))`	`O(V)`

Common pitfalls

Checking only for cycles — a forest (n=3, [[0,1]]) is not a tree.
Checking only the edge count — a cycle plus an isolated node also has n-1 edges.
Using directed DFS cycle detection — in an undirected graph the parent edge is not a cycle.

Interview tips

Lead with the theorem: tree ⇔ connected and exactly n-1 edges.
Remember n = 1 with no edges is a valid tree.
Offer union-find when edges arrive as a stream; BFS when the graph is already built.

Pattern

Union-Find → incremental connectivity and cycle detection in undirected graphs.

My notes saved in this browser