Graph Valid Tree
AmazonThe problem
You have a graph of n nodes labeled from 0 to n - 1.
You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true Explanation: The graph consists of 5 nodes labeled from 0 to 4 and has 4 edges. A valid tree must have exactly n-1 edges, which in this case is 4, so the count is correct. Additionally, there are no cycles because every new edge connects a previously disconnected node. The graph is also fully connected, meaning all nodes can be reached from any other node. Since all conditions of a tree are satisfied, the given graph forms a valid tree.
Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false Explanation: The graph consists of 5 nodes and 5 edges. A valid tree must have exactly n-1 edges, but here there are 5 edges instead of 4, which is already a problem. Additionally, the edge [1,3] forms a cycle because there is already a path from 1 to 3 through 1-2-3. Even though the graph is connected, the presence of a cycle means it does not satisfy the conditions of a tree. Therefore, the given graph is not a valid tree.
Input : n = 3 , edges = [[0,1],[1,2]]
- 1 <= n <= 2000
- 0 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= ai, bi < n
- ai != bi
- There are no self-loops or repeated edges.
cpp
class Solution {
public:
bool validTree(int n, vector<vector<int>>& edges) {
// Your code goes here
}
};java
class Solution {
public boolean validTree(int n, int[][] edges) {
// Your code goes here
}
}python
class Solution(object):
def validTree(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: bool
"""
# Your code goes herejavascript
/**
* @param {number} n
* @param {number[][]} edges
* @return {boolean}
*/
var validTree = function(n, edges) {
// Your code goes here
};csharp
public class Solution
{
public bool ValidTree(int n, List<Tuple<int, int>> edges)
{
// Your code goes here
}
}go
func validTree(n int, edges [][]int) bool {
}Stuck? Show a way to structure it+
- 01Reject immediately unless edge count is n-1
- 02Build adjacency lists or initialize DSU
- 03Traverse from one node or union edges detecting cycles
- 04Verify every node belongs to the same component
Reference answer
Then expect these follow-ups
How do you detect the first cycle with DSU?
Tests: follow-up reasoning
How would this work for directed graphs?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question