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.

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:

11 - 2
2    |
3    3 - 4

This one is an example of one that is not:

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?

xxxxxxxxxx

  console.log('PASSED: ' + 'isGraphTree(4, [[1, 2], [1, 3], [3, 4], [4, 1]])');

var assert = require('assert');

​

function isGraphTree(n, edges) {

  // fill in

  return true;

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

​

var tree4 = new Node(5);

Here's our guided, illustrated walk-through.

How do I use this guide?