> Interview Breeze

Discerning a tree from a graph

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

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

Read More >>
Breadth First Search

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 >>
Binary Tree Column Printer

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 >>

Python Console