Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Graph Valid Tree (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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.

Constraints:

  • 1 <= n <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= a<sub>i</sub> <= b<sub>i</sub> < n
  • a<sub>i</sub> != b<sub>i</sub>
  • There are no self-loops or repeated edges.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible