This problem asks whether a given graph represented by edges forms a valid tree. A valid tree is a connected, acyclic graph. This means:
Two primary approaches effectively solve this: Union-Find and Depth-First Search (DFS).
This approach leverages the Union-Find data structure to efficiently check for cycles and connectivity.
Algorithm:
p
of size n
(number of nodes), where p[i] = i
initially. This represents each node as its own disjoint set.[a, b]
:
a
(find(a)
) and b
(find(b)
).find(a) == find(b)
, a cycle is detected (both nodes belong to the same set), so return false
.p[find(a)] = find(b)
, effectively merging the sets.n
(the number of connected components) because a merge has occurred.n == 1
, all nodes are connected, and there are no cycles, thus it's a valid tree; otherwise, return false
.Time Complexity: O(n*α(n)), where α(n) is the inverse Ackermann function, which is practically a constant. Union-Find operations (find
and union
) have amortized time complexity of almost O(1).
Space Complexity: O(n) to store the parent array.
Code (Python):
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
def find(x: int) -> int:
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(n))
for a, b in edges:
pa, pb = find(a), find(b)
if pa == pb:
return False
p[pa] = pb
n -= 1
return n == 1
Other languages (Java, C++, Go, Javascript) follow a similar structure; only syntax varies.
This approach uses DFS to traverse the graph and detect cycles.
Algorithm:
n - 1
, it cannot be a tree, so return false
.g
representing the graph.vis
set to track visited nodes.false
is returned.vis
is equal to n
, it means all nodes were reachable, and there were no cycles, signifying a valid tree; otherwise return false
.Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. DFS visits each node and edge once.
Space Complexity: O(n) to store the adjacency list and the vis
set.
Code (Python):
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
def dfs(i: int):
vis.add(i)
for j in g[i]:
if j not in vis:
dfs(j)
if len(edges) != n - 1:
return False
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
vis = set()
dfs(0)
return len(vis) == n
Again, other languages would have similar code with syntactic differences. Both Union-Find and DFS offer efficient solutions for this problem. Union-Find usually has a slight edge in performance due to its near-constant-time operations. However, DFS is also quite efficient and might be considered more intuitive for some.