Graph Valid Tree

Explanation & Solution

Description

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

A valid tree must satisfy two conditions:

1. The graph is fully connected (there is exactly one connected component).

2. The graph has no cycles (it has exactly n - 1 edges).

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

Output: true

Explanation: The 5 nodes are all connected with 4 edges and no cycles, forming a valid tree.

Constraints

1 <= n <= 2000
0 <= edges.length <= 5000
edges[i].length == 2
0 <= ai, bi < n
ai != bi
There are no repeated edges.

Approach

Union Find pattern

1. Quick Edge Count Check

A valid tree with n nodes has exactly n - 1 edges
If edges.length !== n - 1, immediately return false
Too few edges means the graph is disconnected; too many means there is a cycle

2. Initialize Union Find

Create a parent array where each node is its own parent
Create a rank array initialized to 0 for union by rank optimization
Initially each node is its own component

3. Implement Find with Path Compression

The find function recursively locates the root of a node's component
Path compression: each visited node is linked directly to the root
Ensures near-constant time for subsequent operations

4. Implement Union by Rank

Find roots of both nodes in the edge
If they share the same root, they are already connected — adding this edge creates a cycle, so return false
Otherwise, attach the smaller-rank tree under the larger-rank tree

5. Process All Edges

For each edge [u, v], attempt union(u, v)
If any union fails (same root), a cycle exists — return false
If all unions succeed and we have exactly n - 1 edges, the graph is a valid tree

6. Return True

All n - 1 edges were processed without creating a cycle
With n - 1 edges and no cycles among n nodes, the graph must be connected
Therefore it is a valid tree

Key Insight

A graph is a valid tree if and only if it has exactly n - 1 edges and no cycles
The edge count check (n - 1) guarantees connectivity when combined with no-cycle verification
Union Find detects cycles: if two nodes already share a root, connecting them creates a cycle

Time

**O(E · α(n))** where E = n - 1, so effectively **O(n)**

Space

O(n) for parent and rank arrays

Visualization

Input:

Connected Components5 nodes, 4 edges

output—

Press play to start connected components

CurrentQueuedVisited

8 steps

Solution Code

Number of Connected Components in an Undirected Graph

Longest Consecutive Sequence