Graph Valid Tree

1. Problem & Core Objective

Given n nodes labelled 0 to n − 1 and a list of undirected edges, determine whether they form a valid tree.

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]   →  true
n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]  →  false   (cycle 1-2-3-1)

Constraints: 1 <= n <= 2000 · 0 <= edges.length <= 5000 · no self-loops, no duplicate edges

What's actually being tested: knowing the two-part definition of a tree — connected and acyclic — and noticing that with the right edge count, checking one implies the other. The counting shortcut is the insight; union-find is the clean way to verify it.

2. First-Principles Thought Process

A tree is two conditions

A graph on n nodes is a tree exactly when it is:

1. connected — one component
2. acyclic — no cycles

Checking both directly is fine. But there's a theorem worth using.

The edge-count shortcut

A connected graph on n nodes has at least n − 1 edges. An acyclic graph on n nodes has at most n − 1 edges.

So a tree has exactly n − 1 edges — and more usefully, the converse:

If a graph has exactly n − 1 edges, then connected ⟺ acyclic.

Which means you only have to check one of the two conditions, provided you first verify the count.

if (edges.length != n - 1) return false;      // cheap rejection
// now: connected ⟺ acyclic, so check either one

Why the count alone isn't enough

n − 1 edges does not imply a tree. With n = 4 and edges [0,1], [1,2], [0,2], that's 3 edges = n − 1, but it's a triangle plus an isolated node 3 — both cyclic and disconnected.

So the count is a necessary condition that lets you skip one of the two checks, not a sufficient one on its own. That's the distinction to state precisely.

Union-find is the natural tool

Process each edge. If both endpoints are already in the same component, adding this edge creates a cycle — reject.

If all n − 1 unions succeed, there's no cycle. Combined with the edge count, that proves it's a tree.

The undirected cycle-detection difference

In a directed graph, question 8 needed three colours. In an undirected graph, DFS sees every edge from both ends, so a naive visited check would call 0—1 a cycle when returning from 1 to 0.

The fixes: track the parent and ignore it, or use union-find, which has no notion of direction and sidesteps the problem entirely.

3. Solution Paths

Approach 1 — DFS for connectivity and cycles separately

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) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }

    boolean[] visited = new boolean[n];
    if (hasCycle(adj, 0, -1, visited)) return false;      // cycle from node 0

    for (boolean v : visited) if (!v) return false;       // disconnected
    return true;
}

private boolean hasCycle(List<List<Integer>> adj, int u, int parent, boolean[] visited) {
    visited[u] = true;
    for (int v : adj.get(u)) {
        if (v == parent) continue;                        // the edge we arrived on
        if (visited[v]) return true;                      // a genuine cycle
        if (hasCycle(adj, v, u, visited)) return true;
    }
    return false;
}

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

Counter-questions on this approach

⭐ "Why the v == parent check, and why is it needed here but not in Course Schedule?"

Because the graph is undirected, so each edge appears in both adjacency lists. Arriving at node 1 from node 0, node 1's list contains 0 — which is already visited. Without the check, every single edge would be reported as a cycle.

In a directed graph that can't happen: 0 → 1 doesn't put 0 in 1's list. That's why question 8 needed three colours instead — the problem there was distinguishing back-edges from cross-edges, which is a different issue entirely.

⭐ "Does v == parent break with duplicate edges?"

Yes, and it's worth knowing. If 0—1 appeared twice, that's a genuine 2-cycle, but the parent check would skip both occurrences and miss it.

The constraints forbid duplicate edges, so it's safe here. To handle them you'd track the edge index used to arrive rather than the node. That's the kind of assumption worth surfacing rather than relying on silently.

"Why does checking visited after one DFS prove connectivity?"

Because a single DFS from node 0 reaches exactly node 0's component. If any node is unvisited afterwards, it's in a different component and the graph is disconnected.

This works only because I start from one node and check afterwards — not by running DFS from every node.

"Where's the missed opportunity?"

It does both checks in full when the edge count makes one of them redundant. Adding if (edges.length != n - 1) return false; first means only one check is needed.

Not an asymptotic saving, but it's the insight the problem is built around.

Approach 2 — Union-Find with the edge-count check (optimal)

public boolean validTree(int n, int[][] edges) {
    if (edges.length != n - 1) return false;        // necessary condition, checked first

    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    for (int[] e : edges) {
        int a = find(parent, e[0]), b = find(parent, e[1]);
        if (a == b) return false;                    // already connected — this edge closes a cycle
        parent[a] = b;                               // union
    }
    return true;                                     // n-1 successful unions, no cycle
}

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

Trace — n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]:

Trace — the cyclic example [[0,1],[1,2],[2,3],[1,3],[1,4]]:

5 edges, but n − 1 = 4 — rejected immediately by the count check, without any union-find work.

• Time O(E · α(n)) — effectively linear · Space O(n)

Counter-questions on this approach

⭐ "Why does the edge count let you skip one of the two checks?"

Because of the theorem: a connected graph needs at least n − 1 edges, and an acyclic graph has at most n − 1. So with exactly n − 1 edges, connected and acyclic become equivalent — proving either one proves both.

Union-find naturally detects cycles, so that's the one I check. If I'd used BFS I'd naturally check connectivity instead. Either is sufficient once the count is verified.

⭐ "Does n − 1 edges alone prove it's a tree?"

No, and this is the precise point. With n = 4 and edges [0,1], [1,2], [0,2] — three edges, so n − 1 — you get a triangle plus an isolated node 3. It's both cyclic and disconnected.

So the count is necessary but not sufficient. What it buys is the equivalence, letting you check one condition instead of two — not a free pass.

⭐ "What does find(a) == find(b) mean, and why is it a cycle?"

They're already in the same component, so a path between them already exists. Adding another edge creates a second path — and two distinct paths between the same pair of nodes is precisely a cycle.

That's the cleanest characterisation: in union-find terms, a cycle is a union that was already unnecessary.

"What is path compression doing?"

On each find, every node on the path to the root is re-pointed directly at the root, flattening the tree. So repeated queries on the same component become O(1) rather than walking a chain.

Combined with union by rank or size it gives O(α(n)) amortised — the inverse Ackermann function, which is below 5 for any n that fits in the observable universe. Effectively constant, though not literally so; I'd state it that way rather than saying O(1).

"This version doesn't use union by rank. Does that matter?"

With path compression alone the amortised bound is O(log n) rather than O(α(n)). At n = 2000 the difference is invisible, and the code is shorter.

For a production implementation I'd add rank or size tracking. Worth mentioning that the two optimisations are independent and both are usually included.

"Could the recursion in find overflow?"

Only with a long unflattened chain, which needs unions performed in an adversarial order without rank. At n = 2000 it's at most 2000 frames — fine. An iterative find with a second pass to compress avoids it entirely.

Approach 3 — BFS connectivity after the count check

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[] visited = new boolean[n];
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(0); visited[0] = true;
    int seen = 1;

    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u))
            if (!visited[v]) { visited[v] = true; seen++; q.offer(v); }
    }
    return seen == n;                       // connected, and n-1 edges => acyclic
}

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

Counter-questions on this approach

⭐ "No cycle check at all. Why is that sound?"

The edge count already ran. With exactly n − 1 edges, connected implies acyclic — so verifying connectivity is a complete proof.

This is the mirror image of the union-find version, which checks acyclicity and gets connectivity for free. Both are valid; which one you check is a matter of which tool fits.

"Why no parent check here?"

Because BFS marks on enqueue and never revisits, so re-encountering a visited node is simply ignored rather than interpreted. There's no cycle detection happening, so there's nothing to get confused by the bidirectional edges.

"Which would you write?"

Union-find, because it's O(n) space with no adjacency list at all — for 5000 edges that's a meaningful saving — and because it generalises to the next two questions. BFS is a fine answer and easier to explain if union-find isn't familiar.

Comparison

4. Why the Optimal Wins

All three are effectively linear, so this is about what you have to build and what you have to check.

The edge-count test is the real content: it turns a two-part definition into a one-part check. After it, verifying either connectivity or acyclicity is a complete proof.

Union-find then needs only an int[n] — no adjacency list, no visited array, no traversal. At 2000 nodes and 5000 edges that's 2000 integers versus a list-of-lists holding 10,000 boxed entries.

The framing worth keeping:

A tree is connected AND acyclic. With exactly n − 1 edges those become equivalent — so check the count first, then verify just one of them. But n − 1 edges alone proves nothing: a triangle plus an isolated node has n − 1 edges and is neither.

5. Java Prerequisites

Union-Find with path compression

int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;       // each node is its own root

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

Cycle detection by union

int a = find(e[0]), b = find(e[1]);
if (a == b) return false;                         // already connected
parent[a] = b;

Union by size — the other standard optimisation, kept separate from compression:

if (size[a] < size[b]) { int t = a; a = b; b = t; }
parent[b] = a; size[a] += size[b];

Undirected adjacency — add both directions:

adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]);

6. Interview Communication Guide

Clarifying questions: Are edges undirected (yes)? Can there be duplicate edges or self-loops (no — and the parent-check approach depends on that)? Is n = 1 with no edges a valid tree (yes — one node, zero edges)? Is the graph guaranteed connected (no — that's half the question)?

The pitch

"A tree is two things: connected and acyclic. I could check both directly, but there's a shortcut worth using.

A connected graph on n nodes needs at least n − 1 edges, and an acyclic graph has at most n − 1. So with exactly n − 1 edges, connected and acyclic become equivalent — proving either one proves both.

So: reject immediately unless edges.length == n - 1, then check one condition.

I'd use union-find, which naturally detects cycles. Process each edge; if both endpoints are already in the same component, a path between them already exists, so this edge creates a second path — that's a cycle, reject. If all n − 1 unions succeed, there's no cycle, and with the edge count that proves it's a tree.

I'd be precise about one thing: n − 1 edges alone doesn't prove a tree. With n = 4 and a triangle 0-1-2 plus an isolated node 3, that's 3 edges — n − 1 — and it's both cyclic and disconnected. The count is necessary, and what it buys is the equivalence, not the conclusion.

O(E · α(n)) with path compression, and O(n) space — no adjacency list needed at all.

If I used DFS instead I'd need the parent check, because the graph is undirected and every edge appears in both adjacency lists — without it, arriving at node 1 from node 0 would see 0 already visited and report a false cycle. That's different from the directed case, which needed three colours for a different reason. Union-find sidesteps direction entirely."

Edge cases to volunteer:

Name the triangle-plus-isolated case. It's the one that proves the count isn't sufficient, and a solution that only checks edges.length == n - 1 returns true for it.

7. Follow-Up Questions — Modified Constraints

⭐ "Count the connected components instead."

Question 11. Start with n components and decrement on every successful union. The count-check and the tree conclusion disappear; the union-find machinery is identical.

⭐ "Find which edge makes it not a tree."

Question 12 — Redundant Connection. Return the first edge whose endpoints are already connected. Union-find gives it directly, and the order matters: the problem asks for the last such edge in input order, which falls out because you process edges in order and the answer is the one that first closes a cycle.

"What if duplicate edges were allowed?"

Union-find handles them correctly — the second copy of 0—1 finds both endpoints already connected and reports a cycle, which is right since two parallel edges form a 2-cycle.

The DFS parent check would miss it, skipping both occurrences. That's a concrete reason to prefer union-find when the input isn't guaranteed clean.

"What if edges were directed?"

Different problem. A directed graph forming a tree means exactly one root with in-degree 0 and every other node with in-degree 1, plus connectivity — and union-find doesn't capture direction. You'd check in-degrees and run a traversal from the root.

"Is it a forest — acyclic but possibly disconnected?"

Drop the edge-count check and just verify no union fails. Any number of edges up to n − 1 is fine; the component count is n minus the number of successful unions.

"What if n were 10^6?"

Union-find scales well — an int[10^6] is 4 MB. I'd switch find to an iterative two-pass version to avoid a million-deep recursion, and add union by size to keep the trees shallow.