91.Graph Valid Tree

MediumBlind 75Graphs · 12/19

Problem

You have n nodes labelled 0 to n - 1 and a list of undirected edges. Determine whether these edges form a valid tree.

A valid tree must satisfy two conditions at the same time: it is connected (every node can reach every other node) and it is acyclic (there is no cycle). Return true if both hold, otherwise false.

Examples

Input:  n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Explanation: 4 edges, all 5 nodes reachable from 0, no cycle.

Input:  n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Explanation: 1 - 2 - 3 - 1 forms a cycle.

Input:  n = 4, edges = [[0,1],[2,3]]
Output: false
Explanation: No cycle, but {0,1} and {2,3} are disconnected.

Constraints

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= a, b < n, a != b
There are no self-loops or repeated edges.

💡 Key Insight

A graph with n nodes is a tree iff it has exactly n - 1 edges and is connected (equivalently: n - 1 edges and no cycle). The edge-count check is O(1) and immediately rejects most bad inputs; after that, a single DFS/BFS checking that all nodes are reached — or a Union-Find that never sees an edge joining two already-connected nodes — finishes the job.

DFS with Parent Tracking

TimeO(V + E)SpaceO(V + E)

Intuition

Run a DFS from node 0. In an undirected graph each edge appears twice in the adjacency list, so going back to the node we just came from is not a cycle. If we ever reach an already-visited node other than our parent, there is a cycle. After DFS, the graph is connected only if we visited all n nodes.

Algorithm

Build an undirected adjacency list.
dfs(node, parent): mark node visited; for every neighbour next:
- skip next == parent;
- if next is visited, return false (cycle);
- else recurse; propagate false.
Return dfs(0, -1) and visitedCount == n.

Visualization

n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

dfs(0, -1) -> dfs(1, 0) -> dfs(2, 1) -> dfs(3, 2)
  at 3: neighbours 2 (parent, skip), 1 (visited, not parent!) -> cycle -> false

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<List<Integer>> adj;
    private boolean[] visited;
    private int visitedCount;

    public boolean validTree(int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        visited = new boolean[n];
        visitedCount = 0;
        // no cycle AND every node reached
        return dfs(0, -1) && visitedCount == n;
    }

    private boolean dfs(int node, int parent) {
        visited[node] = true;
        visitedCount++;
        for (int next : adj.get(node)) {
            if (next == parent) {
                continue; // the edge we arrived on
            }
            if (visited[next]) {
                return false; // reached an ancestor through a different edge: cycle
            }
            if (!dfs(next, node)) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(V + E) — standard DFS.
Space: O(V + E) — adjacency list and recursion stack.

BFS with Edge-Count Check

TimeO(V + E)SpaceO(V + E)

Intuition

Use the theorem: if edges.length != n - 1 the answer is immediately false. With exactly n - 1 edges, the graph is a tree iff it is connected — so we only need to count how many nodes BFS reaches from 0. No parent tracking is required.

Algorithm

If edges.length != n - 1, return false.
Build the adjacency list.
BFS from 0, marking nodes when enqueued and counting them.
Return count == n.

Visualization

n = 4, edges = [[0,1],[2,3]]
edges.length = 2 != n - 1 = 3  -> false immediately

n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]  (4 == n - 1, continue)
BFS from 0: 0 -> {1,2,3} -> {4}   reached 5 == n -> true

Code

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false; // a tree has exactly n - 1 edges
        }
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        boolean[] visited = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        visited[0] = true;
        int count = 1;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : adj.get(node)) {
                if (!visited[next]) {
                    visited[next] = true;
                    count++;
                    queue.offer(next);
                }
            }
        }
        return count == n; // n - 1 edges + connected => tree
    }
}

Complexity

Time: O(V + E) — one BFS (and E = V - 1 after the check).
Space: O(V + E) — adjacency list and queue.

Union-FindOptimal

TimeO(V · α(V))SpaceO(V)

Intuition

Process edges one by one. If an edge connects two nodes that already share a root, adding it would close a cycle — return false. Combined with the n - 1 edge check, "no cycle" guarantees connectivity, so no traversal or adjacency list is needed.

Algorithm

If edges.length != n - 1, return false.
Initialise parent[i] = i.
For each edge [a, b]: if find(a) == find(b) return false; else union them.
Return true.

Dry Run

flowchart TD
    S["n = 5, edges.length = 5<br/>but n - 1 = 4"] -->|"edge count check"| F0["return false"]
    T["n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]<br/>4 == n - 1"] --> A["union 0-1: roots 0,1 differ"]
    A --> B["union 0-2: roots 0,2 differ"]
    B --> C["union 0-3: roots 0,3 differ"]
    C --> D["union 1-4: roots 0,4 differ"]
    D --> R["no cycle found -> return true"]

Code

java

class Solution {
    private int[] parent;
    private int[] rank;

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        for (int[] e : edges) {
            if (!union(e[0], e[1])) {
                return false; // endpoints already connected: cycle
            }
        }
        return true; // n - 1 edges and acyclic => connected tree
    }

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    private boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return false;
        }
        if (rank[rootA] < rank[rootB]) {
            int tmp = rootA;
            rootA = rootB;
            rootB = tmp;
        }
        parent[rootB] = rootA; // attach smaller-rank tree under larger
        if (rank[rootA] == rank[rootB]) {
            rank[rootA]++;
        }
        return true;
    }
}

Complexity

Time: O(V · α(V)) — at most n - 1 near-constant union/find operations.
Space: O(V) — parent and rank arrays.

Complexity Comparison

Approach	Time	Space
DFS with Parent Tracking	O(V + E)	O(V + E)
BFS with Edge-Count Check	O(V + E)	O(V + E)
Union-Find	O(V · α(V))	O(V)

Common Pitfalls

Treating the reverse of the edge you came from as a cycle — in DFS you must skip the parent.
Checking only "no cycle" and forgetting connectivity (e.g. n = 4, edges = [[0,1],[2,3]]).
n = 1 with no edges is a valid tree; 0 == n - 1 handles it naturally.
Running the n - 1 shortcut but then still tracking parents — unnecessary once the count check is in place.