Graph Valid Tree — Graphs Interview Problem

Q: Example 1: What is the output for input n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]?

Output: true. The 5 nodes are all connected through node 0, and there are exactly 4 edges (n-1), forming a valid tree with no cycles.

Q: Example 2: What is the output for input n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]?

Output: false. Nodes 1, 2, and 3 form a cycle (1-2-3-1). A tree cannot contain any cycles.

Q: Example 3: What is the output for input n = 4, edges = [[0,1],[2,3]]?

Output: false. The graph is disconnected — nodes {0,1} and {2,3} are in separate components. A tree must be a single connected component.

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:

The graph is fully connected (there is a path between every pair of nodes).
The graph has no cycles.

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
Explanation: The graph forms a valid tree:
    0
   /|\
  1 2 3
  |
  4
All nodes are connected and there are no cycles.

Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
Output: false
Explanation: There is a cycle: 1 -> 2 -> 3 -> 1.
Even though all nodes are connected, the cycle makes it not a valid tree.

Example 3:

Input: n = 4, edges = [[0,1],[2,3]]
Output: false
Explanation: The graph has two disconnected components:
{0, 1} and {2, 3}. A valid tree must be fully connected.

Examples

Example 1

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

Output: true

Explanation: The 5 nodes are all connected through node 0, and there are exactly 4 edges (n-1), forming a valid tree with no cycles.

Example 2

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

Output: false

Explanation: Nodes 1, 2, and 3 form a cycle (1-2-3-1). A tree cannot contain any cycles.

Example 3

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

Output: false

Explanation: The graph is disconnected — nodes {0,1} and {2,3} are in separate components. A tree must be a single connected component.

Constraints

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

Optimal Complexity

Time

O(V + E)

Space

O(V)

Examples

Constraints

Optimal Complexity

Practice this problem with an AI interviewer