### Problem

Write a function that takes a node and returns `True`

if the node is part of a tree or `False`

if it's part of a graph. For the purpose of this problem, you may assume a node is structured as such:

class Node(): def __init__(self, value, children): self.value = value self.children = children

### Solution

#### Graph versus Tree

In order to solve this problem, we need to consider the difference between a graph and a tree. A tree is actually a specific type of graph known as a minimally connected graph, in which each node has only one path to it. Using this information, we can easily discern a strategy for checking whether the node we are given in our function is a tree or graph by traversing from the given node, keeping track of all visited nodes, and returning False if we come across a node that has been previously visited.

#### Implementation

For our specific implementation, we have used a breadth first search, though you could have also used a depth first search just as easily in this example.

def is_tree(node): seen_nodes = {} queue = [node] while len(queue): next_queue = [] for cur_node in queue: if cur_node in seen_nodes: return False seen_nodes[cur_node] = True if cur_node.children: next_queue += cur_node.children queue = next_queue return True

## You may also want to read:

Depth first search (sometimes referred to as DFS) is an algorithm for traversing a graph or tree.

Read More >>Breadth first search (sometimes referred to as BFS) is an algorithm for traversing a graph or tree. We traverse the tree or graph by examining all nodes at a given level, before moving on to the next level of nodes.

Read More >>Given binary tree, write a function to print its values in column order, from the bottom to top. You can assume that there will be no collisions, in which 2 nodes would occupy the same row and column.

Read More >>