30 / 75
Check if graph is a valid tree: must be connected and have exactly n-1 edges (no cycles).
Example:
Input:
n=5, edges=[[0,1],[0,2],[0,3],[1,4]]Output:
trueCommon Mistakes:
- Not checking edge count first (tree must have exactly n-1 edges)
- Forgetting to track parent in DFS to avoid false cycle detection
- Not verifying graph is fully connected after DFS
- Using directed graph instead of undirected
Notes:
Tree properties: (1) n-1 edges, (2) no cycles, (3) fully connected. Time O(V+E), Space O(V+E). Can also use Union-Find.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Check if graph is a valid tree: must be connected and have exactly n-1 edges (no cycles).
Example:
Input:
n=5, edges=[[0,1],[0,2],[0,3],[1,4]]Output:
trueCommon Mistakes:
- Not checking edge count first (tree must have exactly n-1 edges)
- Forgetting to track parent in DFS to avoid false cycle detection
- Not verifying graph is fully connected after DFS
- Using directed graph instead of undirected
Notes:
Tree properties: (1) n-1 edges, (2) no cycles, (3) fully connected. Time O(V+E), Space O(V+E). Can also use Union-Find.
30/75
Graph Valid Tree