Graph Valid Tree
- 2 min read
- Graph
- LC-Medium
3 years ago
Solution
- Two properties here that make a graph a valid tree:
- No cycles
- The entire graph is a single connected component (i.e. all nodes are connected together)
- Do a Depth-first Search, keep track of visited nodes
- If a loop is found, (i.e. node that's already seen in visited set), return False
- To prevent an already visited neighbour from being considered as a loop, keep tracking of previous node in depth first traversal
- Say you're at node 1. The graph is undirected.
- Neighbours of 1 are both 0 and 4. But 0 should not be considered as it's the node we just came from. Only 4 should be considered.
- When we keep track of the previous node like this, we can immediately know whether or not a node we already saw before was one we already traversed or a cycle exists, which breaks the tree property.
- At the end, check to see if the number of visited nodes is equal to the number of nodes in the tree. If it is, return True
| Time | Space | Explanation |
|---|---|---|
O(n ) | O(n) |
def validTree(self, n: int, edges: List[List[int]]) -> bool:
adj = defaultdict(set)
for a, b in edges:
adj[a].add(b)
adj[b].add(a)
vis = set()
def dfs(node, prev):
if node in vis:
return False
vis.add(node)
for nbr in adj[node]:
if nbr == prev:
continue
if not dfs(nbr, node):
return False
return True
return dfs(0, -1) and len(vis) == n