Problem Statement
Graph Valid Tree
You are given n nodes (numbered 0 to n-1) and a list of undirected edges. An edge like [0,1] means node 0 and node 1 are connected, and "undirected" means the connection goes both ways. Your job is to decide if these edges form a valid tree. A tree is a graph where everything is connected in one piece and there are no loops. Think of a family tree or the branches of a real tree: you can reach every part, and there is exactly one path between any two points, never a circle that brings you back where you started. Two things must both be true for a valid tree: it has exactly n-1 edges, and it has no cycle (no loop). We will check both using a tool called Union-Find.
Signals to notice
Brute force first
Check both connectivity (BFS/DFS) and acyclicity (Union-Find) separately — works but redundant. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
A graph is a tree iff it has exactly n-1 edges AND is connected. Check edge count, then BFS/DFS to verify connectivity. Or use Union-Find: if any edge creates a cycle, it's not a tree. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on n=4, edges=[[0,1],[1,2],[0,2]]
Edge-count check: len(edges)=3 == n-1=3 -> pass, continue
Init parent=[0,1,2,3] (every node is its own root)
Edge (0,1): find(0)=0, find(1)=1, different -> union: parent[0]=1 -> parent=[1,1,2,3]
Edge (1,2): find(1)=1, find(2)=2, different -> union: parent[1]=2 -> parent=[1,2,2,3]
Edge (0,2): find(0)=2 (0->1->2), find(2)=2, SAME root -> cycle found
Return False (3 edges form a cycle on {0,1,2}; node 3 left disconnected)What must stay true
Three equivalent conditions for a tree: (1) connected + acyclic, (2) connected + n-1 edges, (3) acyclic + n-1 edges. Any two of {connected, acyclic, n-1 edges} implies the third. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
if len(edges) != n - 1: return False
parent = [0..n-1] # each node its own root
find(x): follow parent to root (with compression)
for (u, v) in edges:
if find(u) == find(v): return False # cycle
parent[find(u)] = find(v) # union
return True # n-1 edges + no cycle = connected treePseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Only checking n-1 edges without connectivity — a forest (disconnected acyclic graph) also has n-1 edges per component but isn't a single tree. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.