Graph Valid Tree

Share

Determine if given n nodes and edges form a valid tree (connected + no cycle).

Example 1
Input: n=5, edges=[[0,1],[0,2],[0,3],[1,4]] → Output: true
Example 2
Input: n=5, edges=[[0,1],[1,2],[2,3],[1,3],[1,4]] → Output: false

Solution Approach

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
Java
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)