Good afternoon! 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:
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 nodesn
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
83
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);
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?