Problem Statement

Given a number n, which indicates the number of nodes numbered from 0 to n-1, and a list of undirected edges for the graph, determine if the graph is a valid tree.

A graph qualifies as a valid tree if it meets the following criteria:

1. It has no cycles.
2. It is fully connected.

Examples

• Example 1:

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

• Expected Output: true

• Justification: There are no cycles in the graph, and all nodes are connected, forming a valid tree.

• Example 2:

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

• Expected Output: false

• Justification: There is a cycle in the graph (0-1-2-3-0), thus it's not a valid tree.

• Example 3:

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

• Expected Output: false

• Justification: TNode 4 is not connected to any other node, making the graph not fully connected.

Constraints:

• 1 <= n <= 2000
• 0 <= edges.length <= 5000
• edges[i].length == 2
• 0 <= a_i <= b_i < n
• a_i != b_i
• There are no self-loops or repeated edges.

Try it yourself

Try solving this question here: