Mark As Completed Discussion

Good evening! Here's our prompt for today.

Given an undirected graph, can you see if it's a tree? If so, return true and false otherwise.

Description

An undirected graph is a tree based on the following conditions: first, there cannot be a cycle. Second, the graph must be connected.

This is an example of a graph that is a tree:

SNIPPET
11 - 2
2    |
3    3 - 4

This one is an example of one that is not:

SNIPPET
1         1
2        / \
3       2 - 3
4      /
5     4

You'll be given two parameters: n for number of nodes, and a multidimensional array of edges like such: [[1, 2], [2, 3]], each pair representing the vertices connected by the edge.

Constraints

  • Number of vertices in the graph <= 100000
  • Number of edges <= 100000
  • The array edges can be empty
  • Expected time complexity : O(|V| + |E|) where |V| be the number of nodes n in the graph and |E| to be the number of edges in the graph
  • Expected space complexity : O(|V|)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

We'll now take you through what you need to know.

How do I use this guide?