← Back to DSA Animator
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.