Loading…

mediumGraphsLC #261Sometimes asked

Graph Valid Tree

Q: How do you solve Graph Valid Tree using the Union-Find (Disjoint Set Union) approach?

When to use it: The cleanest answer. Phrase it as 'merge nodes; if an edge joins two already-connected nodes, that's a cycle — and n−1 successful unions means one component'. Union-Find decides tree-ness by tracking which nodes are already connected. **Edge-count fast check.** A tree on n nodes has exactly n−1 edges: fewer can't span all nodes (forces disconnection), more guarantees a cycle (pigeonhole). So if `edges.length != n − 1`, return false immediately. This single line eliminates both the 'too few' and 'too many' failure modes. **Detecting a cycle while merging.** Start with each node in its own set. For each edge (a, b), find the roots of a and b. If they're already equal, a and b were already connected by some earlier path — adding this edge closes a loop, i.e. a cycle — so return false. Otherwise union the two sets. With the edge-count guard in place, surviving all edges without a collision means the graph is acyclic. **Why acyclic + n−1 edges ⇒ tree.** It's a classic equivalence: among graphs on n nodes, any two of {connected, acyclic, n−1 edges} imply the third. We verify n−1 edges (the guard) and acyclic (no union collision); connectivity follows for free. So no separate connectivity scan is needed. **The optimisations that make it near-linear.** *Path compression* flattens the tree during `find` so future lookups are fast; *union by rank* attaches the shorter tree under the taller to keep depth tiny. Together they give the inverse-Ackermann bound — effectively constant per operation. Time complexity: O(E · α(n)) ≈ O(E + n). Space complexity: O(n).

Q: How do you solve Graph Valid Tree using the DFS / BFS with Parent Tracking approach?

When to use it: Offer as the traversal-based alternative. Emphasise parent tracking for undirected cycle detection and the final 'visited all n nodes' connectivity check. Verify both tree properties with one traversal plus a count. **Build adjacency, traverse from one node.** Construct an undirected adjacency list. Launch DFS (or BFS) from node 0, marking nodes visited. If the graph is connected, this lone traversal reaches all n nodes. **Undirected cycle detection needs the parent.** When exploring node `u`'s neighbours, you'll encounter the node you just came from (`u`'s parent) because the edge is undirected. That's *not* a cycle — it's the same edge seen from the other side. A real cycle is reaching an already-visited node that is *not* the parent. So pass the parent down and skip it; flag a cycle on any other visited neighbour. **Connectivity = visited count.** After the traversal, compare the number of visited nodes to n. If fewer than n were visited, the graph is disconnected (the false example with two components), so it's not a tree even if acyclic. **Both checks are required.** Acyclic alone isn't enough (a forest is acyclic but disconnected); connected alone isn't enough (a connected graph can have cycles). A tree is precisely the conjunction, which this traversal verifies in one shot. Time complexity: O(V + E). Space complexity: O(V + E).

LCPractice

Graphs · 6 of 34 · 10 min

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [aᵢ, bᵢ] indicates that there is an undirected edge between nodes aᵢ and bᵢ in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

In plain English

A valid tree is a connected, acyclic undirected graph. Equivalently, n nodes form a tree exactly when there are n−1 edges and the graph is connected (or, n−1 edges and acyclic). We must confirm both connectivity and the absence of cycles.

Examples

Example 1

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Note: 4 edges = n−1, connected and acyclic — a valid tree rooted conceptually at 0.

Example 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Note: 5 edges > n−1; the edges 1-2-3-1 form a cycle, so it's not a tree.

Example 3

Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Note: Only 2 edges and two disconnected components — acyclic but not connected.

Constraints

1 ≤ n ≤ 2000
0 ≤ edges.length ≤ 5000
edges[i].length == 2
0 ≤ aᵢ, bᵢ < n
aᵢ != bᵢ (no self-loops)
There are no duplicate edges

Clarifying questions4First question: Is the graph undirected?Explore questions

Q1.Is the graph undirected?
Yes. That matters for cycle detection: in DFS I must track the parent so the edge I arrived on isn't mistaken for a cycle.
Q2.Are self-loops or duplicate edges possible?
No per constraints (aᵢ ≠ bᵢ, no duplicates). Either would create an immediate cycle and fail the tree test.
Q3.Does a single node with no edges count as a tree?
Yes — n = 1, 0 edges is a trivially valid tree (connected and acyclic).
Q4.Can I use the edge-count shortcut?
Yes — a tree must have exactly n−1 edges. If edges.length ≠ n−1 I can return false immediately, then just verify acyclicity/connectivity.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A graph with n nodes is a tree iff it is fully connected AND has no cycle. Two equivalent checks: (1) exactly n−1 edges plus connectivity, or (2) no cycle plus connectivity. Union-Find is cleanest: if any edge connects two nodes already in the same set, there's a cycle → false; finally verify a single component. O(E·α(n)) ≈ O(E + n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the tree characterisation (connected + acyclic ⇔ n−1 edges + connected) and can verify it with Union-Find or a parent-aware DFS, including the edge-count shortcut.

Where candidates slip

Checking only one property (e.g. acyclic but not connected, or n−1 edges but not verifying connectivity when edge count differs), or in undirected DFS flagging the parent edge as a cycle.

How to stand out

State both equivalent characterisations, use the n−1 edge-count fast check, implement Union-Find with path compression + union by rank, and mention the parent-tracked DFS alternative and why parent tracking matters.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Union-Find (Disjoint Set Union)	`O(E · α(n)) ≈ O(E + n)`	`O(n)`	The cleanest answer. Phrase it as 'merge nodes; if an edge joins two already-connected nodes, that's a cycle — and n−1 successful unions means one component'.	Read
2	DFS / BFS with Parent TrackingOptimal	`O(V + E)`	`O(V + E)`	Offer as the traversal-based alternative. Emphasise parent tracking for undirected cycle detection and the final 'visited all n nodes' connectivity check.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewIs it a valid tree?edges == n-1?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Union-Find (Disjoint Set Union)

TimeO(E · α(n)) ≈ O(E + n)SpaceO(n)

The cleanest answer. Phrase it as 'merge nodes; if an edge joins two already-connected nodes, that's a cycle — and n−1 successful unions means one component'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the minimum number of edges to connect n nodes with no cycle? That count is a quick necessary condition.

2Hint 2Explore hint

Process edges one by one, merging the two endpoints' sets. When does adding an edge create a cycle?

3Hint 3Explore hint

If both endpoints already share a root, the edge closes a loop → cycle → not a tree. With exactly n−1 edges and no such collision, the graph is one connected acyclic component — a tree.

A · Core idea

Union-Find decides tree-ness by tracking which nodes are already connected.

Edge-count fast check. A tree on n nodes has exactly n−1 edges: fewer can't span all nodes (forces disconnection), more guarantees a cycle (pigeonhole). So if edges.length != n − 1, return false immediately. This single line eliminates both the 'too few' and 'too many' failure modes.

Detecting a cycle while merging. Start with each node in its own set. For each edge (a, b), find the roots of a and b. If they're already equal, a and b were already connected by some earlier path — adding this edge closes a loop, i.e. a cycle — so return false. Otherwise union the two sets. With the edge-count guard in place, surviving all edges without a collision means the graph is acyclic.

Why acyclic + n−1 edges ⇒ tree. It's a classic equivalence: among graphs on n nodes, any two of {connected, acyclic, n−1 edges} imply the third. We verify n−1 edges (the guard) and acyclic (no union collision); connectivity follows for free. So no separate connectivity scan is needed.

The optimisations that make it near-linear. Path compression flattens the tree during find so future lookups are fast; union by rank attaches the shorter tree under the taller to keep depth tiny. Together they give the inverse-Ackermann bound — effectively constant per operation.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

init

each its own root

node ↓

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

Reference implementation previewpublic boolean validTree(int n, int[][] edges) { if (edges.length != n - 1) return false; // necessary condition int[] parent = new int[n]; int[] rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i;Explore the full code

solution.javaJava

Union-Find (Disjoint Set Union) — reference

5 teaching notes

1
public boolean validTree(int n, int[][] edges) {
2
    if (edges.length != n - 1) return false; // necessary condition
3
    int[] parent = new int[n];
4
    int[] rank = new int[n];
5
    // Each node starts as its own set (its own root).
6
    for (int i = 0; i < n; i++) parent[i] = i;
7
    for (int[] e : edges) {
8
        if (!union(parent, rank, e[0], e[1])) {
9
            return false; // endpoints already connected → cycle
10
        }
11
    }
12
    return true; // n-1 edges + acyclic ⇒ connected tree
13
}
14
 
15
private int find(int[] parent, int x) {
16
    while (parent[x] != x) {
17
        // Flatten the tree during find so subsequent lookups are near-constant.
18
        parent[x] = parent[parent[x]]; // path compression
19
        x = parent[x];
20
    }
21
    return x;
22
}
23
 
24
private boolean union(int[] parent, int[] rank, int a, int b) {
25
    int ra = find(parent, a), rb = find(parent, b);
26
    if (ra == rb) return false; // cycle
27
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28
    parent[rb] = ra;
29
    // Union by rank: increase rank only when merging equal-height trees, keeping depth
30
    // small.
31
    if (rank[ra] == rank[rb]) rank[ra]++;
32
    return true;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(E · α(n)) ≈ O(E + n) timeO(n) spaceOpen the invariant and proofExplore the proof

Union-Find answers 'are these two already connected?' in near-constant time, which is exactly the cycle question for undirected graphs: an edge between two already-connected nodes is redundant and forms a loop. Pair that with the n−1 edge count and you've checked both tree properties in a single sweep.

ComplexityO(E · α(n)) ≈ O(E + n) time, O(n) space — With path compression and union by rank, each find/union is effectively O(α(n)) (inverse Ackermann, practically constant). Processing E edges is O(E·α(n)); the parent/rank arrays are O(n) space.

E · Edge cases and pitfalls6n = 1, edges = [] — edges.length 0 == n−1 = 0; no unions; single connected acyclic node → true.Explore edge cases

Edge cases handled

n = 1, edges = []edges.length 0 == n−1 = 0; no unions; single connected acyclic node → true.
n = 2, edges = [[0,1]]1 edge == n−1; one union, no collision → true.
n = 4, edges = [[0,1],[2,3]]2 edges != n−1 = 3 → false immediately (disconnected).

Pitfalls

Skipping the edge-count check and then forgetting to verify connectivity separately.
Implementing find without path compression on large inputs — degrades toward O(n) per op.
Treating it like a directed-graph problem — this is undirected; a same-root edge is the cycle signal.

03.2

Approach 2 of 2 · Optimal

DFS / BFS with Parent Tracking

TimeO(V + E)SpaceO(V + E)

Offer as the traversal-based alternative. Emphasise parent tracking for undirected cycle detection and the final 'visited all n nodes' connectivity check.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build an adjacency list. Traverse from node 0 — if the graph is a tree, this single traversal should reach every node.

2Hint 2Explore hint

Detect a cycle during traversal: if you reach an already-visited node that ISN'T the one you came from, you've found a loop.

3Hint 3Explore hint

After the traversal, the graph is a tree iff you visited all n nodes (connected) and never hit a non-parent revisit (acyclic).

A · Core idea

Verify both tree properties with one traversal plus a count.

Build adjacency, traverse from one node. Construct an undirected adjacency list. Launch DFS (or BFS) from node 0, marking nodes visited. If the graph is connected, this lone traversal reaches all n nodes.

Undirected cycle detection needs the parent. When exploring node u's neighbours, you'll encounter the node you just came from (u's parent) because the edge is undirected. That's not a cycle — it's the same edge seen from the other side. A real cycle is reaching an already-visited node that is not the parent. So pass the parent down and skip it; flag a cycle on any other visited neighbour.

Connectivity = visited count. After the traversal, compare the number of visited nodes to n. If fewer than n were visited, the graph is disconnected (the false example with two components), so it's not a tree even if acyclic.

Both checks are required. Acyclic alone isn't enough (a forest is acyclic but disconnected); connected alone isn't enough (a connected graph can have cycles). A tree is precisely the conjunction, which this traversal verifies in one shot.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Disconnected graph fails the visited-count check

dfs(0, parent=-1)

Active call / nodeSupporting contextReturned stateNot active

DFS from 0 reaches only {0,1}; nodes 2,3 stay unvisited → not a tree.

Final resultfalse

C · Code with teaching comments

solution.javaJava

DFS / BFS with Parent Tracking — optimal

4 teaching notes

1
public boolean validTree(int n, int[][] edges) {
2
    if (edges.length != n - 1) return false;
3
    List<List<Integer>> adj = new ArrayList<>();
4
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
5
    for (int[] e : edges) {
6
        adj.get(e[0]).add(e[1]);
7
        adj.get(e[1]).add(e[0]);
8
    }
9
    boolean[] visited = new boolean[n];
10
    if (hasCycle(adj, visited, 0, -1)) return false;
11
    for (boolean v : visited) {
12
        if (!v) return false; // disconnected
13
    }
14
    return true;
15
}
16
 
17
private boolean hasCycle(List<List<Integer>> adj, boolean[] visited,
18
                         int node, int parent) {
19
    visited[node] = true;
20
    for (int nb : adj.get(node)) {
21
        if (nb == parent) continue;        // the edge we came in on
22
        if (visited[nb]) return true;      // revisit of non-parent → cycle
23
        if (hasCycle(adj, visited, nb, node)) return true;
24
    }
25
    return false;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proof

The parent pointer is what separates 'the edge I arrived on' from 'a genuine second route to this node'. Forgetting it makes every undirected edge look like a 2-cycle. With it, DFS cleanly distinguishes a tree's single-path-between-any-two-nodes property from a graph's redundant paths.

ComplexityO(V + E) time, O(V + E) space — Building the adjacency list is O(V + E). DFS/BFS visits each node once and each undirected edge twice → O(V + E). The adjacency list and visited set are O(V + E) space.

E · Edge cases and pitfalls6n = 1, edges = [] — DFS from 0 visits the one node; all(visited) → true.Explore edge cases

Edge cases handled

n = 1, edges = []DFS from 0 visits the one node; all(visited) → true.
cycle presentDFS hits a visited non-parent neighbour → returns false.
two componentsSingle DFS leaves some node unvisited → false.

Pitfalls

Not tracking the parent — every undirected edge looks like a 2-cycle, false-positives everywhere.
Checking acyclicity but skipping the connectivity (visited-count) check — a forest would pass.
Recursing without the edge-count guard on huge inputs — deep recursion; consider BFS.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic 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) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting parent tracking in undirected DFS

An undirected edge appears in both nodes' adjacency lists, so the child sees the parent as a visited neighbour. Without skipping the parent, every edge is falsely reported as a cycle.

Explore the code comparison

Don't write this

def has_cycle(node):
    visited[node] = True
    for nb in adj[node]:
        if visited[nb]:
            return True       # flags the parent edge as a cycle
        if has_cycle(nb):
            return True
    return False

Write this instead

def has_cycle(node, parent):
    visited[node] = True
    for nb in adj[node]:
        if nb == parent:
            continue
        if visited[nb]:
            return True
        if has_cycle(nb, node):
            return True
    return False

Checking only acyclicity, not connectivity

A graph can be acyclic yet disconnected (a forest). Returning true just because no cycle was found accepts forests like n=4, edges=[[0,1],[2,3]].

Explore the code comparison

Don't write this

if (hasCycle(adj, visited, 0, -1)) return false;
return true; // ignores disconnected nodes

Write this instead

if (hasCycle(adj, visited, 0, -1)) return false;
for (boolean v : visited) if (!v) return false; // connectivity
return true;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Tree validation via Union-Find (or DFS): connected + acyclic

Code pattern to memorize

if len(edges) != n - 1: return False   # necessary shortcut
for (a, b) in edges:
    if find(a) == find(b): return False  # cycle
    union(a, b)
return True   # n-1 edges + no cycle ⇒ connected tree

Rules to remember

1A tree on n nodes has exactly n−1 edges — fewer can't connect all, more forces a cycle. Check this first as a fast reject.
2With n−1 edges, the graph is a tree iff it's acyclic (which then implies connected) — so 'n−1 edges + no cycle' is sufficient.
3Union-Find: a cycle appears when an edge joins two nodes that already share a root.
4DFS/BFS alternative: traverse from node 0; it's a tree iff you visit all n nodes with no revisit of a non-parent (undirected cycle check).
5For undirected DFS cycle detection, track the parent to avoid mistaking the edge you came in on for a cycle.

Use this pattern when

Validating tree structure (connected + acyclic) on an undirected graph
Counting connected components / detecting union of sets
Dynamic connectivity ('are these two nodes joined yet?')
Undirected cycle detection

Choose another pattern when

Directed graph cycle/order → topological sort (Course Schedule), not undirected Union-Find
Edge weights / MST → Kruskal uses Union-Find but the goal differs
Grid adjacency implicit graph → flood fill is simpler than building a DSU

Interview takeaway

Graph Valid Tree distills the definition of a tree into two checkable facts: connected and acyclic, equivalent to 'n−1 edges and connected'. Union-Find detects the cycle and connectivity in one near-linear pass — the same DSU that powers Number of Connected Components and Kruskal's MST.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTree validation = connected + acyclic ⇔ n−1 edges + connected. Union-Find checks both in near-linear time; parent-tracked DFS/BFS is the traversal alternative. Same DSU family as Number of Connected Components and Redundant Connection.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of Connected Components in an Undirected Graph
Same Union-Find; count distinct roots instead of validating a single tree.
Redundant Connection
Coming soon
Union-Find: return the edge whose endpoints already share a root (the cycle-closing edge).
Number of Operations to Make Network Connected
Coming soon
Union-Find components minus one = cables to move (need n−1 edges total).
Course Schedule
Directed cousin: cycle detection via topological sort rather than undirected Union-Find.

Same pattern

←

Rotting Oranges

Continue · Next problem

Number of Connected Components in an Undirected Graph

mediumGraphsLC #261Sometimes asked

Graph Valid Tree

LCPractice

Graphs · 6 of 34 · 10 min

Return true if the edges of the given graph make up a valid tree, and false otherwise.

In plain English

Examples

Example 1

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Note: 4 edges = n−1, connected and acyclic — a valid tree rooted conceptually at 0.

Example 2

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Note: 5 edges > n−1; the edges 1-2-3-1 form a cycle, so it's not a tree.

Example 3

Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Note: Only 2 edges and two disconnected components — acyclic but not connected.

Constraints

1 ≤ n ≤ 2000
0 ≤ edges.length ≤ 5000
edges[i].length == 2
0 ≤ aᵢ, bᵢ < n
aᵢ != bᵢ (no self-loops)
There are no duplicate edges

Clarifying questions4First question: Is the graph undirected?Explore questions

Q1.Is the graph undirected?
Yes. That matters for cycle detection: in DFS I must track the parent so the edge I arrived on isn't mistaken for a cycle.
Q2.Are self-loops or duplicate edges possible?
No per constraints (aᵢ ≠ bᵢ, no duplicates). Either would create an immediate cycle and fail the tree test.
Q3.Does a single node with no edges count as a tree?
Yes — n = 1, 0 edges is a trivially valid tree (connected and acyclic).
Q4.Can I use the edge-count shortcut?
Yes — a tree must have exactly n−1 edges. If edges.length ≠ n−1 I can return false immediately, then just verify acyclicity/connectivity.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the tree characterisation (connected + acyclic ⇔ n−1 edges + connected) and can verify it with Union-Find or a parent-aware DFS, including the edge-count shortcut.

Where candidates slip

Checking only one property (e.g. acyclic but not connected, or n−1 edges but not verifying connectivity when edge count differs), or in undirected DFS flagging the parent edge as a cycle.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Union-Find (Disjoint Set Union)	`O(E · α(n)) ≈ O(E + n)`	`O(n)`	The cleanest answer. Phrase it as 'merge nodes; if an edge joins two already-connected nodes, that's a cycle — and n−1 successful unions means one component'.	Read
2	DFS / BFS with Parent TrackingOptimal	`O(V + E)`	`O(V + E)`	Offer as the traversal-based alternative. Emphasise parent tracking for undirected cycle detection and the final 'visited all n nodes' connectivity check.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Union-Find (Disjoint Set Union)

TimeO(E · α(n)) ≈ O(E + n)SpaceO(n)

The cleanest answer. Phrase it as 'merge nodes; if an edge joins two already-connected nodes, that's a cycle — and n−1 successful unions means one component'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What's the minimum number of edges to connect n nodes with no cycle? That count is a quick necessary condition.

2Hint 2Explore hint

Process edges one by one, merging the two endpoints' sets. When does adding an edge create a cycle?

3Hint 3Explore hint

If both endpoints already share a root, the edge closes a loop → cycle → not a tree. With exactly n−1 edges and no such collision, the graph is one connected acyclic component — a tree.

A · Core idea

Union-Find decides tree-ness by tracking which nodes are already connected.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

init

each its own root

node ↓

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resulttrue

C · Code with teaching comments

solution.javaJava

Union-Find (Disjoint Set Union) — reference

5 teaching notes

1
public boolean validTree(int n, int[][] edges) {
2
    if (edges.length != n - 1) return false; // necessary condition
3
    int[] parent = new int[n];
4
    int[] rank = new int[n];
5
    // Each node starts as its own set (its own root).
6
    for (int i = 0; i < n; i++) parent[i] = i;
7
    for (int[] e : edges) {
8
        if (!union(parent, rank, e[0], e[1])) {
9
            return false; // endpoints already connected → cycle
10
        }
11
    }
12
    return true; // n-1 edges + acyclic ⇒ connected tree
13
}
14
 
15
private int find(int[] parent, int x) {
16
    while (parent[x] != x) {
17
        // Flatten the tree during find so subsequent lookups are near-constant.
18
        parent[x] = parent[parent[x]]; // path compression
19
        x = parent[x];
20
    }
21
    return x;
22
}
23
 
24
private boolean union(int[] parent, int[] rank, int a, int b) {
25
    int ra = find(parent, a), rb = find(parent, b);
26
    if (ra == rb) return false; // cycle
27
    if (rank[ra] < rank[rb]) { int t = ra; ra = rb; rb = t; }
28
    parent[rb] = ra;
29
    // Union by rank: increase rank only when merging equal-height trees, keeping depth
30
    // small.
31
    if (rank[ra] == rank[rb]) rank[ra]++;
32
    return true;
33
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.33 lines

D · Why it works and complexityO(E · α(n)) ≈ O(E + n) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6n = 1, edges = [] — edges.length 0 == n−1 = 0; no unions; single connected acyclic node → true.Explore edge cases

Edge cases handled

n = 1, edges = []edges.length 0 == n−1 = 0; no unions; single connected acyclic node → true.
n = 2, edges = [[0,1]]1 edge == n−1; one union, no collision → true.
n = 4, edges = [[0,1],[2,3]]2 edges != n−1 = 3 → false immediately (disconnected).

Pitfalls

Skipping the edge-count check and then forgetting to verify connectivity separately.
Implementing find without path compression on large inputs — degrades toward O(n) per op.
Treating it like a directed-graph problem — this is undirected; a same-root edge is the cycle signal.

03.2

Approach 2 of 2 · Optimal

DFS / BFS with Parent Tracking

TimeO(V + E)SpaceO(V + E)

Offer as the traversal-based alternative. Emphasise parent tracking for undirected cycle detection and the final 'visited all n nodes' connectivity check.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Build an adjacency list. Traverse from node 0 — if the graph is a tree, this single traversal should reach every node.

2Hint 2Explore hint

Detect a cycle during traversal: if you reach an already-visited node that ISN'T the one you came from, you've found a loop.

3Hint 3Explore hint

After the traversal, the graph is a tree iff you visited all n nodes (connected) and never hit a non-parent revisit (acyclic).

A · Core idea

Verify both tree properties with one traversal plus a count.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Interactive diagram

Disconnected graph fails the visited-count check

dfs(0, parent=-1)

Active call / nodeSupporting contextReturned stateNot active

DFS from 0 reaches only {0,1}; nodes 2,3 stay unvisited → not a tree.

Final resultfalse

C · Code with teaching comments

solution.javaJava

DFS / BFS with Parent Tracking — optimal

4 teaching notes

1
public boolean validTree(int n, int[][] edges) {
2
    if (edges.length != n - 1) return false;
3
    List<List<Integer>> adj = new ArrayList<>();
4
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
5
    for (int[] e : edges) {
6
        adj.get(e[0]).add(e[1]);
7
        adj.get(e[1]).add(e[0]);
8
    }
9
    boolean[] visited = new boolean[n];
10
    if (hasCycle(adj, visited, 0, -1)) return false;
11
    for (boolean v : visited) {
12
        if (!v) return false; // disconnected
13
    }
14
    return true;
15
}
16
 
17
private boolean hasCycle(List<List<Integer>> adj, boolean[] visited,
18
                         int node, int parent) {
19
    visited[node] = true;
20
    for (int nb : adj.get(node)) {
21
        if (nb == parent) continue;        // the edge we came in on
22
        if (visited[nb]) return true;      // revisit of non-parent → cycle
23
        if (hasCycle(adj, visited, nb, node)) return true;
24
    }
25
    return false;
26
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.26 lines

D · Why it works and complexityO(V + E) timeO(V + E) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6n = 1, edges = [] — DFS from 0 visits the one node; all(visited) → true.Explore edge cases

Edge cases handled

n = 1, edges = []DFS from 0 visits the one node; all(visited) → true.
cycle presentDFS hits a visited non-parent neighbour → returns false.
two componentsSingle DFS leaves some node unvisited → false.

Pitfalls

Not tracking the parent — every undirected edge looks like a 2-cycle, false-positives everywhere.
Checking acyclicity but skipping the connectivity (visited-count) check — a forest would pass.
Recursing without the edge-count guard on huge inputs — deep recursion; consider BFS.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting parent tracking in undirected DFS

An undirected edge appears in both nodes' adjacency lists, so the child sees the parent as a visited neighbour. Without skipping the parent, every edge is falsely reported as a cycle.

Explore the code comparison

Don't write this

def has_cycle(node):
    visited[node] = True
    for nb in adj[node]:
        if visited[nb]:
            return True       # flags the parent edge as a cycle
        if has_cycle(nb):
            return True
    return False

Write this instead

def has_cycle(node, parent):
    visited[node] = True
    for nb in adj[node]:
        if nb == parent:
            continue
        if visited[nb]:
            return True
        if has_cycle(nb, node):
            return True
    return False

Checking only acyclicity, not connectivity

A graph can be acyclic yet disconnected (a forest). Returning true just because no cycle was found accepts forests like n=4, edges=[[0,1],[2,3]].

Explore the code comparison

Don't write this

if (hasCycle(adj, visited, 0, -1)) return false;
return true; // ignores disconnected nodes

Write this instead

if (hasCycle(adj, visited, 0, -1)) return false;
for (boolean v : visited) if (!v) return false; // connectivity
return true;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Tree validation via Union-Find (or DFS): connected + acyclic

Code pattern to memorize

if len(edges) != n - 1: return False   # necessary shortcut
for (a, b) in edges:
    if find(a) == find(b): return False  # cycle
    union(a, b)
return True   # n-1 edges + no cycle ⇒ connected tree

Rules to remember

1A tree on n nodes has exactly n−1 edges — fewer can't connect all, more forces a cycle. Check this first as a fast reject.
2With n−1 edges, the graph is a tree iff it's acyclic (which then implies connected) — so 'n−1 edges + no cycle' is sufficient.
3Union-Find: a cycle appears when an edge joins two nodes that already share a root.
4DFS/BFS alternative: traverse from node 0; it's a tree iff you visit all n nodes with no revisit of a non-parent (undirected cycle check).
5For undirected DFS cycle detection, track the parent to avoid mistaking the edge you came in on for a cycle.

Use this pattern when

Validating tree structure (connected + acyclic) on an undirected graph
Counting connected components / detecting union of sets
Dynamic connectivity ('are these two nodes joined yet?')
Undirected cycle detection

Choose another pattern when

Directed graph cycle/order → topological sort (Course Schedule), not undirected Union-Find
Edge weights / MST → Kruskal uses Union-Find but the goal differs
Grid adjacency implicit graph → flood fill is simpler than building a DSU

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of Connected Components in an Undirected Graph
Same Union-Find; count distinct roots instead of validating a single tree.
Redundant Connection
Coming soon
Union-Find: return the edge whose endpoints already share a root (the cycle-closing edge).
Number of Operations to Make Network Connected
Coming soon
Union-Find components minus one = cables to move (need n−1 edges total).
Course Schedule
Directed cousin: cycle detection via topological sort rather than undirected Union-Find.

Same pattern

←

Rotting Oranges

Continue · Next problem

Number of Connected Components in an Undirected Graph