Graph Valid Tree (medium)

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]]
Image
  • 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]]]]
Image
  • 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]]
Image
  • Expected Output: false

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

Try it yourself

Try solving this question here:

Python3
Python3

. . .