Determine if given n nodes and edges form a valid tree (connected + no cycle).
Input: n=5, edges=[[0,1],[0,2],[0,3],[1,4]] → Output: true
Input: n=5, edges=[[0,1],[1,2],[2,3],[1,3],[1,4]] → Output: false
Tree has exactly n-1 edges and is connected. Use Union-Find to detect cycles.
- Check edges.length == n-1 (necessary condition)
- Union-Find: for each edge try to union
- If already connected (same root): cycle exists, return false
- After all edges: check all nodes connected
public boolean validTree(int n, int[][] edges) {
if (edges.length != n - 1) return false;
int[] parent = new int[n];
Arrays.fill(parent, -1);
for (int[] e : edges) {
int ra = find(parent, e[0]), rb = find(parent, e[1]);
if (ra == rb) return false;
parent[ra] = rb;
}
return true;
}
private int find(int[] parent, int x) {
return parent[x] == -1 ? x : (parent[x] = find(parent, parent[x]));
}
- Time Complexity: O(n * alpha(n))
- Space Complexity: O(n)