Graph Valid Tree
Problem
Given an integer n and a list of edges representing an undirected graph, determine if the graph is a valid tree, meaning it is connected and contains no cycles.
- 1 ≤ n ≤ 10⁴
- 0 ≤ edges.length ≤ 10⁴
- edges[i].length == 2
- 0 ≤ edges[i][j] < n
- No duplicate edges
- No self-loops
Example
n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]trueThe graph has 5 nodes and 4 edges, which is n-1 edges, a necessary condition for a tree. Starting DFS from node 0, all nodes are visited without encountering a cycle. The graph is connected and acyclic, so it is a valid tree.
Approach
Straightforward Solution
A brute-force approach might check all possible subsets of edges to find a spanning tree, which is exponential and infeasible. Alternatively, one might attempt to detect cycles without verifying connectivity, which can lead to false positives.
Core Observation
A valid tree with n nodes must have exactly n-1 edges and be fully connected without cycles. The absence of cycles can be detected by DFS with a parent tracking mechanism, and connectivity is verified by ensuring all nodes are visited.
Path to Optimal
PreviewThe key recognition signals are 'valid tree', 'connected', and 'no cycles'. These indicate a graph traversal approach with cycle detection…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewBuild an adjacency list to represent the graph. Perform a DFS starting from node 0, passing the previous node to avoid revisiting the immediate parent…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n + e)
Building the adjacency list takes O(e). DFS visits each node and edge once, resulting in O(n + e) total time.
Space
O(n + e)
The adjacency list stores all edges, requiring O(n + e) space. The visited set stores up to n nodes. The recursion stack can go up to O(n) in the worst case.
Pattern Spotlight
DFS (Cycle Detection and Connectivity Check)
When verifying if an undirected graph is a tree, use DFS to detect cycles by tracking the parent node to avoid false positives from bidirectional edges, and confirm connectivity by ensuring all nodes are visited.
Solution
| 1 | class Solution:
|
| 2 | def validTree(self, n: int, edges: list[list[int]]) -> bool:
|
| 3 | if not n:
|
| 4 | return True
|
| 5 |
|
| 6 | adj = {i: [] for i in range(n)}
|
| 7 | for n1, n2 in edges:
|
| 8 | adj[n1].append(n2)
|
| 9 | adj[n2].append(n1)
|
| 10 |
|
| 11 | visit = set()
|
| 12 | def dfs(i, prev):
|
| 13 | if i in visit:
|
| 14 | return False
|
| 15 |
|
| 16 | visit.add(i)
|
| 17 | for j in adj[i]:
|
| 18 | if j == prev:
|
| 19 | continue
|
| 20 | if not dfs(j, i):
|
| 21 | return False
|
| 22 | return True
|
| 23 |
|
| 24 | return dfs(0, -1) and n == len(visit) |
Step-by-Step Solution
Construct Adjacency List to Represent the Graph
| 6 | adj = {i: [] for i in range(n)}
|
| 7 | for n1, n2 in edges:
|
| 8 | adj[n1].append(n2)
|
| 9 | adj[n2].append(n1)
|
Objective
To build a graph representation that enables efficient traversal and neighbor lookup.
Key Insight
An adjacency list is the most space- and time-efficient way to represent sparse graphs. It allows quick access to neighbors of any node, which is essential for DFS traversal. Initializing the adjacency list with empty lists for all nodes ensures all nodes are accounted for, even isolated ones.
Interview Quick-Check
Core Logic
The adjacency list maps each node to a list of its neighbors, enabling O(1) average-time neighbor access during DFS.
Common Pitfalls & Bugs
Forgetting to add edges in both directions for an undirected graph leads to incorrect traversal and missed connections.
Detect Cycles and Track Visited Nodes Using DFS with Parent Tracking
To recursively explore the graph, detect cycles, and mark nodes as visited to verify connectivity.
Verify Full Connectivity and Return Final Result
To confirm that all nodes are reachable from the starting node and that no cycles were detected.
Handle Edge Case of Zero Nodes
To immediately return true if the graph has no nodes, as an empty graph is trivially a valid tree.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 8 Critical lines interviewers watch for.
if i in visit:Check if current node has already been visited.
Encountering a visited node during DFS (other than the parent) indicates a cycle, so returning false here detects cycles early.
if j == prev:Skip the neighbor if it is the previous node.
Ignoring the edge back to the parent prevents false cycle detection caused by bidirectional edges in undirected graphs.
return dfs(0, -1) and n == len(visit)Return true if DFS from node 0 found no cycles and all nodes were visited.
Combining cycle detection with connectivity check ensures the graph is a valid tree, as both conditions are necessary and sufficient.
Full line-by-line criticality + rationale for all 18 lines available on Pro.
Test Your Understanding
Why is it necessary to track the previous node during DFS when detecting cycles in an undirected graph?
See the answer with Pro.
Related Problems
DFS pattern
Don't just read it. Drill it.
Reconstruct Graph Valid Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Graph Valid Tree drill