Python implementation of various types of trees

trees.py

import contextlib


@contextlib.contextmanager
def raises(exception):
    try:
        yield
    except exception as e:
        assert True
    else:
        assert False


class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []


class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if value > self.value:
            if self.right:
                self.right.insert(value)
            else:
                self.right = BinarySearchTreeNode(value)

        if value < self.value:
            if self.left:
                self.left.insert(value)
            else:
                self.left = BinarySearchTreeNode(value)

        if value == self.value:
            raise Exception(
                "This BST implementation does not permit duplicate values.")


def is_binary_search_tree(node):
    if not node:
        return True

    if node.left and node.left.value > node.value:
        return False

    if node.right and node.right.value < node.value:
        return False

    return is_binary_search_tree(node.left) and is_binary_search_tree(node.right)


#   3
#  / \
# 2   4

root = BinaryTreeNode(3)
root.left = BinaryTreeNode(2)
root.right = BinaryTreeNode(4)

assert is_binary_search_tree(root) is True

#   3
#  /
# 4

root = BinaryTreeNode(3)
root.left = BinaryTreeNode(4)

assert is_binary_search_tree(root) is False

#   3
#    \
#     2

root = BinaryTreeNode(3)
root.right = BinaryTreeNode(2)

assert is_binary_search_tree(root) is False

#   3
#  / \
# 2   4

root = BinarySearchTreeNode(3)
root.insert(2)
root.insert(4)

assert is_binary_search_tree(root) is True


#   3
#  /
# 4

root = BinarySearchTreeNode(3)
root.left = BinarySearchTreeNode(4)

assert is_binary_search_tree(root) is False

#   3
#  /
# 3

root = BinarySearchTreeNode(3)

with raises(Exception):
    root.insert(3)


def in_order_traversal(node):
    if node.left:
        in_order_traversal(node.left)

    print(node.value)

    if node.right:
        in_order_traversal(node.right)


def pre_order_traversal(node):
    print(node.value)

    if node.left:
        pre_order_traversal(node.left)

    if node.right:
        pre_order_traversal(node.right)


def post_order_traversal(node):
    if node.left:
        post_order_traversal(node.left)

    if node.right:
        post_order_traversal(node.right)

    print(node.value)


root = BinarySearchTreeNode(3)
root.insert(2)
root.insert(4)

in_order_traversal(root)  # => 2 3 4
pre_order_traversal(root)  # => 3 2 4
post_order_traversal(root)  # => 2 4 3


class GraphNode:
    def __init__(self, value):
        self.value = value
        self.neighbors = []

    def __str__(self):
        return str(self.value)


root = GraphNode(1)
root.neighbors = [GraphNode(2), GraphNode(3)]
root.neighbors[0].neighbors = [GraphNode(4), GraphNode(5)]
root.neighbors[1].neighbors = [GraphNode(6), root]


def depth_first_search(node, value, visited=[]):
    if node.value == value:
        return True

    visited.append(node)

    for neighbor in node.neighbors:
        if neighbor in visited:
            continue

        if depth_first_search(neighbor, value, visited):
            return True

    return False


assert depth_first_search(root, 6) is True
assert depth_first_search(root, 7) is False


def breadth_first_search(node, value):
    queue = [node]
    visited = []

    while len(queue):
        node = queue.pop()

        if node.value == value:
            return True

        visited.append(node)

        for neighbor in node.neighbors:
            if neighbor not in visited:
                queue.append(neighbor)

    return False


assert breadth_first_search(root, 6) is True
assert breadth_first_search(root, 7) is False