LeetCode 261. Graph Valid Tree

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true
Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

Tree vs Graph

  1. It is connected
  2. It has no cycle.
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
from collections import defaultdict
graph = defaultdict(list)

# build the graph
for src, dest in edges:
graph[src].append(dest)
graph[dest].append(src)

visited = set()
def dfs(root, parent): # returns true if graph has no cycle
visited.add(root)
for node in graph[root]:
if node == parent: # trivial cycle, skip
continue
if node in visited:
return False

if not dfs(node, root):
return False
return True

return dfs(0, -1) and len(visited) == n
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
from collections import defaultdict
graph = defaultdict(list)

# build the graph
for src, dest in edges:
graph[src].append(dest)
graph[dest].append(src)

visited = set()f
def dfs(root):
visited.add(root)
for node in graph[root]:
if node in visited:
continue
dfs(node)

dfs(0)
return len(visited) == n and len(edges) == n - 1

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store