Mark As Completed Discussion

Good morning! 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

Here's how we would solve this problem...

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.