Graph Valid Tree
Problem Statement
Given n
nodes labeled from 0
to n - 1
and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
Example 1:
Input:n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Output:True
Example 2:
Input:n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
Output:False
Note:
- You can assume that no duplicate edges will appear in edges. Since all edges are
undirected
,[0, 1]
is the same as[1, 0]
and thus will not appear together in edges.
Constraints:
1 <= n <= 100
0 <= edges.length <= n * (n - 1) / 2
You should aim for a solution as good or better than O(V + E)
time and O(V + E)
space, where V
is the number vertices and E
is the number of edges in the graph.
Recommended Time and Space Complexity
You should aim for a solution as good or better than O(V + E)
time and O(V + E)
space, where V
is the number vertices and E
is the number of edges in the graph.
Hint 1
According to the definition of a tree, a tree is an undirected graph with no cycles, all the nodes are connected as one component, and any two nodes have exactly one path. Can you think of a recursive algorithm to detect a cycle in the given graph and ensure it is a tree?
Hint 2
We can use the Depth First Search (DFS) algorithm to detect a cycle in the graph. Since a tree has only one component, we can start the DFS from any node, say node 0
. During the traversal, we recursively visit its neighbors (children). If we encounter any already visited node that is not the parent of the current node, we return false as it indicates a cycle. How would you implement this?
Hint 3
We start DFS from node 0
, assuming -1
as its parent. We initialize a hash set visit
to track the visited nodes in the graph. During the DFS, we first check if the current node is already in visit
. If it is, we return false, detecting a cycle. Otherwise, we mark the node as visited and perform DFS on its neighbors, skipping the parent node to avoid revisiting it. After all DFS calls, if we have visited all nodes, we return true, as the graph is connected. Otherwise, we return false because a tree must contain all nodes.
Solution
Cycle Detection (DFS)
def valid_tree(n: int, edges: list[list[int]]) -> bool: if len(edges) > (n - 1): return False
adj = [[] for _ in range(n)] for u, v in edges: adj[u].append(v) adj[v].append(u)
visited = set()
def dfs(node, parent): if node in visited: return False
visited.add(node) for neighbor in adj[node]: if neighbor == parent: continue if not dfs(neighbor, node): return False return True
return dfs(0, -1) and len(visited) == n
Time complexity: O(V + E)
Space complexity: O(V + E)
Where
V
is the number vertices andE
is the number of edges in the graph.
Breadth First Search
from collections import deque
def valid_tree_bfs(n: int, edges: list[list[int]]) -> bool: if len(edges) > n - 1: return False
adj = [[] for _ in range(n)] for u, v in edges: adj[u].append(v) adj[v].append(u)
visited = set() queue = deque([(0, -1)]) # (current node, parent node) visited.add(0)
while queue: node, parent = queue.popleft() for neighbor in adj[node]: if neighbor == parent: continue if neighbor in visited: return False visited.add(neighbor) queue.append((neighbor, node))
return len(visited) == n
Time complexity: O(V + E)
Space complexity: O(V + E)
Where
V
is the number vertices andE
is the number of edges in the graph.
Disjoint Set Union
class DisjointSetUnion: def __init__(self, n): self.components = n self.parent = list(range(n)) self.size = [1] * n
def find(self, node): if self.parent[node] != node: self.parent[node] = self.find(self.parent[node]) return self.parent[node]
def union(self, u, v): parent_u = self.find(u) parent_v = self.find(v) if parent_u == parent_v: return False
self.components -= 1 if self.size[parent_u] < self.size[parent_v]: parent_u, parent_v = parent_v, parent_u self.size[parent_u] += self.size[parent_v] self.parent[parent_v] = parent_u return True
def get_components(self): return self.components
def valid_tree_dsu(n: int, edges: list[list[int]]) -> bool: if len(edges) > n - 1: return False
dsu = DisjointSetUnion(n) for u, v in edges: if not dsu.union(u, v): return False return dsu.get_components() == 1
Time complexity: O(V + (E * A(V)))
Space complexity: O(V)
Where
V
is the number of vertices andE
is the number of edges in the graph.A()
is used for amortized complexity.