DSA AnimatorDSA animations
Is Graph a Tree? GFG Medium Graph · Union-Find
Problem

Tree = connected + acyclic. Tree has exactly n-1 edges. Use Union-Find: if edge connects same root → cycle → not tree.

Example
Input: n=5, edges=[[0,1],[0,2],[0,3],[3,4]]
Output: true
Try Examples
Custom: n / edges (a-b)
Approach
Union-Find
Tree: n-1 edges and no cycle. If find(a)==find(b) when adding edge (a,b) → cycle. Else union.
Graph & Parent Array
Load an example.
Variables
Edge
—
find(a)
—
find(b)
—
parent[]
—
Step Logic
Press ▶ Play or Next Step.
✓
Ready
0/0
Select example and Play.
Algorithm
1
edges != n-1 → false
2
parent[i]=i, union each edge
3
find(a)==find(b) → cycle → false
Time
O(n·α(n))
Space
O(n)
Why n-1 Edges

Tree: connected + acyclic. n nodes need n-1 edges to connect. More → cycle. Less → disconnected.

How to solve Is Graph a Tree?

GFG · Medium · Graph · Pattern: Union Find

Why the obvious approach is slow

You could run a search from every node to look for cycles and check connectivity separately. There is a much simpler test.

The key idea

A tree with n nodes always has exactly n −1 edges. So if the edge count is not n −1, it cannot be a tree. With exactly n −1 edges, it is a tree if and only if there is no cycle. Use union find: for each edge, if both ends already have the same root, that edge closes a cycle. Otherwise, merge the two groups.

Remember

Tree means n −1 edges and no cycle. Union find detects a cycle the moment an edge joins a group to itself.

Run the animation above on your own input, or watch the 1:55 video explanation of Is Graph a Tree? with a dry run and Java code.

More Graph problems