Course4all
Join us on telegram
Home/dsa/Union Find/Graph Valid Tree

Graph Valid Tree

Master this topic with zero to advance depth.

Graph Valid Tree

Given nn nodes and a list of undirected edges, determine if these edges form a valid tree. A tree is a connected graph with no cycles.

Medium
Approach 1

Level I: BFS (Connectivity & Reachability)

Intuition

A graph is a tree if it has exactly n−1n-1 edges and all nodes are connected. Check edge count first, then use BFS to ensure all nn nodes are reachable from node 0.

⏱ O(V + E)💾 O(V + E)

Detailed Dry Run

n=5, edges=4. Correct. Start BFS from 0. Visit 1, 2, 3. From 1 visit 4. Visited size = 5. True.

java
import java.util.*;
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if(edges.length != n-1) return false;
        List<Integer>[] adj = new ArrayList[n]; for(int i=0; i<n; i++) adj[i]=new ArrayList<>();
        for(int[] e:edges) { adj[e[0]].add(e[1]); adj[e[1]].add(e[0]); }
        Queue<Integer> q = new LinkedList<>(); q.add(0); Set<Integer> vis = new HashSet<>(); vis.add(0);
        while(!q.isEmpty()) { int u=q.poll(); for(int v:adj[u]) if(vis.add(v)) q.add(v); }
        return vis.size() == n;
    }
}
Approach 2

Level III: Union-Find (Cycle Detection)

Intuition

Use DSU to process edges. If an edge (u,v)(u, v) connects two nodes already in the same component, a cycle exists. If no cycles and edges = n−1n-1, it's a tree.

⏱ O(V \cdot \alpha(V))💾 O(V)

Detailed Dry Run

Edge [0,1]: Union(0,1). Edge [0,2]: Union(0,2). Edge [1,2]: Find(1)=0, Find(2)=0. Same root! Cycle! False.

java
class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        int[] p = new int[n]; for (int i = 0; i < n; i++) p[i] = i;
        for (int[] e : edges) {
            int r1 = find(p, e[0]), r2 = find(p, e[1]);
            if (r1 == r2) return false;
            p[r1] = r2;
        }
        return true;
    }
    private int find(int[] p, int i) { return p[i] == i ? i : (p[i] = find(p, p[i])); }
}
← Previous QuestionNumber of Islands
Next Question →Number of Provinces