# 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`

--

--

## More from Algo.Monster

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator

Love podcasts or audiobooks? Learn on the go with our new app.

## Algo.Monster

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator