Description
Decide whether a simple undirected graph with n >= 1 labeled vertices is a tree.
Solution
def valid_tree(n, edges):
if len(edges) != n-1:
return False
graph = [[] for _ in range(n)]
for a,b in edges:
graph[a].append(b)
graph[b].append(a)
seen, stack = {0}, [0]
while stack:
for node in graph[stack.pop()]:
if node not in seen:
seen.add(node)
stack.append(node)
return len(seen) == nExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[3,[[0,1],[1,2]]]- Output
true
The graph is connected with two edges for three vertices.
Example 2
- Input
[3,[[0,1],[1,2],[2,0]]]- Output
false
The extra edge creates a cycle.
Example 3
- Input
[1,[]]- Output
true
One isolated vertex is a valid tree.
Approach
Require exactly n-1 edges, then confirm every vertex is reachable from vertex zero.
Time & space
O(V + E) time; O(V + E) auxiliary space for V vertices and E edges.