Graph Valid Tree

Share

Given n nodes labeled 0 to n-1 and a list of undirected edges, determine whether these edges form a valid tree. A valid tree has exactly n-1 edges and is fully connected with no cycles.

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

A valid tree must have exactly n-1 edges AND be connected. Use Union-Find: if any edge creates a cycle (both nodes already connected), return false.

  • If edges.length != n-1: return false.
  • Union-Find on n nodes.
  • For each edge: if same component already (find(u)==find(v)): cycle detected, return false.
  • Else union. Return true.
Java
class Solution {
    int[] parent;
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int pu = find(e[0]), pv = find(e[1]);
            if (pu == pv) return false;
            parent[pu] = pv;
        }
        return true;
    }
    private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
}
  • Time Complexity: O(N + E)
  • Space Complexity: O(N)