Two conditions to check:
Exactly edges (necessary for any tree)
No cycles (every union should succeed)
function validTree(n, edges):
if edges.length != n - 1:
return false
uf = new UnionFind(n)
for each (u, v) in edges:
if not uf.union(u, v):
return false // cycle detected
return true
if you have exactly edges and no cycles, the graph must be connected. Why? An acyclic graph with nodes and edges has exactly one component (any more components would require fewer edges).
Time: . Space: .