# LeetCode 261. Graph Valid Tree

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 = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]Output: true`

Example 2:

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

Before solving the problem, we have to know the definitions.

# Tree vs Graph

A tree is a special undirected graph. It satisfy two properties

1. It is connected
2. It has no cycle.

Being connected means you can start from any node and reach any other node. To prove it, we can do a DFS and add each node we visit to a set. After we visited all the nodes, we compare the number of nodes in the set with the total number of nodes. If they are the same then every node is accessible from any other node and the graph is connected.

To prove an undirected graph having no cycle, we can also do a DFS. If a graph contains a cycle, then we would visit a certain node more than once. There is a minor caveat, since the graph is undirected, when we visit a child we would always add parent to the next visit list. This creates a trivial cycle and not the real cycle we want. We can avoid detecting trivial cycle but adding an additional `parent` state in the DFS call.

We can check both properties in one DFS call since cycle detection always keeps track of a visited set.

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

Alternative Solution

There’s actually an even simpler version. Condition 2 no cycle can also be expressed as `# of nodes == # of edges + 1`.

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