Introduction

Graph Valid Tree is a classic Union Find problem.

You are given:

  • n nodes labeled from 0 to n-1
  • Undirected edges

Goal:

Determine whether the graph forms a valid tree.

A valid tree must:

  • Be connected
  • Contain no cycles

Example

Input

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

Output

true

Explanation

0|\
| \
1  2
|
4
|
3

All nodes are connected and no cycle exists.

Key Observation

A graph is a valid tree only if:

  • Number of edges = n - 1
  • No cycle exists

Union Find helps detect cycles efficiently.

Algorithm

  1. Check if edges count equals n - 1.
  2. Initialize DSU.
  3. Process every edge.
  4. If both nodes have same parent, cycle found.
  5. Otherwise union them.
  6. If no cycle exists, return true.

Dry Run

Input

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

Edge (0,1)

Union

Edge (0,2)

Union

Edge (0,3)

Union

Edge (1,4)

Union

No cycle found.

Number of edges:

4 = n - 1

Answer:

true

Approach : Union Find (DSU)

Start with every node as its own component.

If an edge connects two nodes already belonging to the same component, a cycle exists.

If no cycle exists and edges count equals n-1, the graph is a valid tree.

Practice

Complexity Analysis

Time Complexity: O(n × α(n))Explanation:Each Union and Find operation takes nearly constant time due to path compression. Every edge is processed once.

Space Complexity: O(n)
Explanation:An additional parent array of size n is used for the Union Find structure.

Why This Problem is Important

Graph Valid Tree combines cycle detection and connectivity checking, making it a fundamental Union Find interview problem.

Common Beginner Mistakes

  • Forgetting edge count must be n-1.
  • Not checking cycles.
  • Incorrect DSU initialization.
  • Using DFS without verifying connectivity.

Interview Tip

Always mention:

A graph is a valid tree if and only if it contains exactly n-1 edges and has no cycles.

Related Questions

  • Redundant Connection
  • Number of Connected Components
  • Accounts Merge
  • Number of Provinces
  • Kruskal's Algorithm

Final Takeaway

Graph Valid Tree is a classic DSU problem that teaches graph connectivity, cycle detection, and tree validation. It is one of the most common Union Find interview questions.