Graph Valid Tree (LC 261)

Pattern: Union-Find (DSU) or DFS — tree validation
Difficulty: Medium (Premium on LeetCode; classic Blind 75)
Key Concept: An undirected graph on n labeled nodes 0..n-1 is a tree iff it is connected and has exactly n-1 edges with no cycles — equivalently: n-1 edges + connected + acyclic.

Problem Statement

Given n nodes and list edges of undirected edges [u, v], return true iff the graph is a valid tree.

Input: int n, int[][] edges
Output: boolean

Tree conditions:

1. Exactly n - 1 edges (for n ≥ 1).
2. No cycles.
3. Fully connected (one component).

---

1. Algorithm & Pseudocode

Brute force

Build adjacency list; from node 0 run BFS/DFS counting visited nodes. Check visited == n and edges.length == n - 1. For cycle, use DFS with parent tracking or union-find on all edges — O(n²) if adjacency built poorly; typically O(n + m) with m = edges.length.

Optimal

Union-Find

if edges.length != n - 1: return false   // quick fail

init DSU of n nodes
for each (u,v) in edges:
  if find(u) == find(v): return false   // cycle
  union(u,v)

return true   // n-1 edges + no cycle => connected tree for simple graph

Note: For n nodes, tree ⇒ m = n-1 and connected. If m = n-1 and no cycle, the graph is a tree (connected) — prove: acyclic + n nodes + n-1 edges ⇒ exactly one component.

DFS cycle check + connectivity

if edges.length != n - 1: return false
build adjacency
visited = 0
dfs(u, parent):
  mark u visited
  for v in adj[u]:
    if v == parent: continue
    if v already visited: cycle -> fail
    dfs(v, u)

start dfs from 0
return visited == n

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Too many edges (> n-1) ⇒ cannot be a tree (trees are minimally connected).
• Too few edges (< n-1) ⇒ cannot connect all n nodes.
• With exactly n-1 edges, any cycle means some edge is redundant ⇒ disconnected component exists elsewhere, or the structure breaks tree definition — union-find detects first redundant edge that closes a cycle.
• Edge case n = 1, edges = [] → empty graph is a single-node tree → true.

---

3. The Dry Run

n = 4, edges = [[0,1],[1,2],[2,3]] — path (tree).

Step	Edge	DSU find before union	Action
—	—	—	edges.length == 3 == n-1 ✓
1	0-1	different	union
2	1-2	different	union
3	2-3	different	union

No premature equal roots → true.

n = 4, edges = [[0,1],[1,2],[2,0]] — only 3 edges but triangle among 0,1,2; node 3 isolated.

Step	Edge	find
1	0-1	union
2	1-2	union
3	2-0	find(2)==find(0) → cycle → false

---

4. Java Solution

Brute Force

Adjacency + DFS with parent (same asymptotic as optimal; “brute” here means more bookkeeping than DSU for some):

import java.util.*;

class SolutionBrute {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] e : edges) {
            adj[e[0]].add(e[1]);
            adj[e[1]].add(e[0]);
        }
        boolean[] vis = new boolean[n];
        if (hasCycle(0, -1, adj, vis)) return false;
        for (int i = 0; i < n; i++) if (!vis[i]) return false;
        return true;
    }

    private boolean hasCycle(int u, int p, List<Integer>[] adj, boolean[] vis) {
        vis[u] = true;
        for (int v : adj[u]) {
            if (v == p) continue;
            if (vis[v]) return true;
            if (hasCycle(v, u, adj, vis)) return true;
        }
        return false;
    }
}

Time: O(n + m), Space: O(n + m).

Optimal

Union-Find

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;

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

        for (int[] e : edges) {
            int u = e[0], v = e[1];
            int pu = find(parent, u), pv = find(parent, v);
            if (pu == pv) return false;
            parent[pu] = pv;
        }
        return true;
    }

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

Time: O(n α(n)) ≈ O(n), Space: O(n).

---

5. The “Java vs. Others” Edge

• Check edges.length == n - 1 first — O(1) reject.
• Union by rank / size plus path compression is standard Java interview polish.
• Multi-edges / self-loops: problem usually guarantees simple graph; if not, add checks u == v or duplicate edge handling.

---

6. Complexity Summary

Approach	Time	Space	Notes
DFS cycle + full visit	O(n + m)	O(n + m)	m must be n-1 for tree
Union-Find	O(n α(n))	O(n)	Very clean

---

ASCII: Tree vs cycle vs disconnected

Valid tree (n=4):        Invalid (cycle):       Invalid (forest):

   0                         0                      0   2
   |                        / \                      |   |
   1                       1---2                     1   3
   |
   2
   |
   3