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

​

def is_graph_tree(n, edges):

    return n

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

​

​

# Regular binary trees

tree1 = Node(4)

tree1.left = Node(1)

tree1.right = Node(3)

​

tree2 = Node(5)

tree2.left = Node(10)

tree2.left.left = Node(17)

tree2.left.right = Node(3)

tree2.right = Node(8)

​

# Binary search trees

tree3 = Node(6)

tree3.left = Node(3)

​

tree4 = Node(5)

tree4.left = Node(3)

Here's our guided, illustrated walk-through.

How do I use this guide?