from collections import deque

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

    def breadth_first_traverse(self):
        breadth_first_queue = deque()
        breadth_first_queue.append(self)
        while breadth_first_queue:
            node = breadth_first_queue.popleft()
            print(node.value)
            for child in node.children:
                if child is not None:
                    breadth_first_queue.append(child)

    def breadth_first_search(self, value):
        breadth_first_queue = deque()
        breadth_first_queue.append(self)
        while breadth_first_queue:
            node = breadth_first_queue.popleft()
            if node.value == value:
                return node
            for child in node.children:
                if child is not None:
                    breadth_first_queue.append(child)

    def depth_first_traverse(self):
        print(self.value)
        for child in self.children:
            if child is not None:
                child.depth_first_traverse()

    def depth_first_search(self, value):
        if (value == self.value):
            return self
        for child in self.children:
            if child is not None:
                node = child.depth_first_search(value)
                if node is not None:
                    return node
        return None

    def __str__(self):
        return self._str_helper("", True, False)

    def _str_helper(self, prefix, tail, newline=True):
        result = ""

        if newline:
            result += "\n"

        self_prefix = (
            type(self).__name__ + prefix + ("└── " if tail else "├── ") 
        )
        result += self_prefix + str(self.value)

        child_prefix = prefix + ("    " if tail else "|   ")
        result += self._str_children(child_prefix)

        return result

    def _str_children(self, prefix):
        result = ""

        none_padding = " " * len(type(self).__name__)
        for child in self.children[:-1]:
            if child is None:
                result += type(self)._str_none(none_padding + prefix, False)
            else:
                result += child._str_helper(prefix, False)
        if self.children:
            last_child = self.children[-1]
            if last_child is None:
                result += type(self)._str_none(none_padding + prefix, True)
            else:
                result += self.children[-1]._str_helper(prefix, True)

        return result

    @staticmethod
    def _str_none(prefix, tail):
        return "\n" + prefix + ("└── " if tail else "├── ")

# old way with extra newline at end
#    def __str__(self):
#        return self._str_helper("", True)
#
#    def _str_helper(self, prefix, tail):
#        result = ""
#
#        self_prefix = (
#            type(self).__name__ + prefix + ("└── " if tail else "├── ") 
#        )
#        result += self_prefix + str(self.value) + "\n"
#
#        child_prefix = prefix + ("    " if tail else "|   ")
#
#        none_padding = " " * len(type(self).__name__)
#        for child in self.children[:-1]:
#            if child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               False)
#            else:
#                result += child._str_helper(child_prefix, False)
#        if self.children:
#            last_child = self.children[-1]
#            if last_child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               True)
#            else:
#                result += self.children[-1]._str_helper(child_prefix, True)
#
#        return result
#
#    @staticmethod
#    def _str_none(prefix, tail):
#        return prefix + ("└── " if tail else "├── ") + "\n"

class BinaryTreeNode(TreeNode):
    def __init__(self, value, left_child=None, right_child=None):
        super().__init__(value, [left_child, right_child])

    @property
    def left_child(self):
        return self.children[0]

    @left_child.setter
    def left_child(self, value):
        self.children[0] = value

    def has_left_child(self):
        return self.left_child is not None

    @property
    def right_child(self):
        return self.children[1]

    @right_child.setter
    def right_child(self, value):
        self.children[1] = value

    def has_right_child(self):
        return self.right_child is not None

    def is_binary_search_tree_node(self, lower_bound=None, upper_bound=None):
        if (
            (lower_bound is not None and self.value <= lower_bound) or
            (upper_bound is not None and upper_bound <= self.value)
        ):
            return False
        if (
            self.has_left_child() and
            not self.left_child.is_binary_search_tree_node(lower_bound,
                                                           self.value)
        ):
            return False
        if (
            self.has_right_child() and
            not self.right_child.is_binary_search_tree_node(self.value,
                                                            upper_bound)
        ):
            return False
        return True

    @classmethod
    def create_from_tree_node(cls, tree_node):
        children = tree_node.children

        left_child = children[0] if len(children) > 0 else None
        if left_child is not None:
            left_child = cls.create_from_tree_node(left_child)

        right_child = children[1] if len(children) > 1 else None
        if right_child is not None:
            right_child = cls.create_from_tree_node(right_child)

        binary_tree_node = cls(tree_node.value, left_child, right_child)
        return binary_tree_node

class BinaryCousinTreeNode(BinaryTreeNode):
    def __init__(self, value, left_child=None, right_child=None,
                 left_cousin=None, right_cousin=None):
        super().__init__(value, left_child, right_child)
        self.left_cousin = left_cousin
        self.right_cousin = right_cousin

    def _str_helper(self, prefix, tail, newline=True):
        result = ""

        if newline:
            result += "\n"

        self_prefix = (
            type(self).__name__ + prefix + ("└── " if tail else "├── ") 
        )
        result += self_prefix + str(self.value)

        left_cousin = "" if self.left_cousin is None else self.left_cousin.value
        right_cousin = (
            "" if self.right_cousin is None else self.right_cousin.value
        )
        cousins = "({}, {})".format(left_cousin, right_cousin)
        result += cousins

        child_prefix = prefix + ("    " if tail else "|   ")
        result += self._str_children(child_prefix)

        return result

# old way with extra newline at end
#    def _str_helper(self, prefix, tail):
#        result = ""
#
#        self_prefix = (
#            type(self).__name__ + prefix + ("└── " if tail else "├── ") 
#        )
#
#        left_cousin = "" if self.left_cousin is None else self.left_cousin.value
#        right_cousin = (
#            "" if self.right_cousin is None else self.right_cousin.value
#        )
#        cousins = "({}, {})".format(left_cousin, right_cousin)
#
#        result += self_prefix + str(self.value) + cousins + "\n"
#
#        child_prefix = prefix + ("    " if tail else "|   ")
#
#        none_padding = " " * len(type(self).__name__)
#        for child in self.children[:-1]:
#            if child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               False)
#            else:
#                result += child._str_helper(child_prefix, False)
#        if self.children:
#            last_child = self.children[-1]
#            if last_child is None:
#                result += type(self)._str_none(none_padding + child_prefix,
#                                               True)
#            else:
#                result += self.children[-1]._str_helper(child_prefix, True)
#
#        return result

    @classmethod
    def create_from_binary_tree_node(cls, binary_tree_node):
        binary_cousin_tree_node = cls(binary_tree_node.value,
                                      binary_tree_node.left_child,
                                      binary_tree_node.right_child)

        breadth_first_queue = deque()
        breadth_first_queue.append([binary_cousin_tree_node])
        level = 0
        while breadth_first_queue:
            level_nodes = breadth_first_queue.popleft()
            cls.link_cousins(level_nodes)
            next_level_nodes = []
            for node in level_nodes:
                for i, child in enumerate(node.children):
                    if child is not None:
                        binary_cousin_tree_child = cls(child.value,
                                                       child.left_child,
                                                       child.right_child)
                        node.children[i] = binary_cousin_tree_child
                        next_level_nodes.append(binary_cousin_tree_child)
            if next_level_nodes:
                breadth_first_queue.append(next_level_nodes)
            level += 1

        return binary_cousin_tree_node

    @staticmethod
    def link_cousins(nodes):
        if not nodes:
            return
        elif len(nodes) < 2:
            nodes[0].left_cousin = None
            nodes[0].right_cousin = None
        else:
            nodes[0].left_cousin = None
            nodes[0].right_cousin = nodes[1]

            for i, node in enumerate(nodes[1:-1], 1):
                node.left_cousin = nodes[i - 1]
                node.right_cousin = nodes[i + 1]

            nodes[-1].left_cousin = nodes[-2]
            nodes[-1].right_cousin = None

class BinarySearchTreeNode(BinaryTreeNode):
    def put(self, value):
        if value < self.value:
            if self.has_left_child():
                self.left_child.put(value)
            else:
                self.left_child = type(self)(value)
        elif value == self.value:
            return
        else:
            if self.has_right_child():
                self.right_child.put(value)
            else:
                self.right_child = type(self)(value)

    def search(self, value):
        if value < self.value and self.has_left_child():
            node = self.left_child.search(value)
            return node
        elif value == self.value:
            return self
        elif self.has_right_child():
            node = self.right_child.search(value)
            return node
        return None

class Tree:
    def __init__(self):
        self.root = None

    def breadth_first_traverse(self):
        self.root.breadth_first_traverse()

    def breadth_first_search(self, value):
        return self.root.breadth_first_search(value)

    def depth_first_traverse(self):
        self.root.depth_first_traverse()

    def depth_first_search(self, value):
        return self.root.depth_first_search(value)

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

    @classmethod
    def create_from_root(cls, root):
        tree = cls()
        tree.root = root
        return tree

class BinaryTree(Tree):
    def is_binary_search_tree(self):
        return self.root is None or self.root.is_binary_search_tree_node()

    @classmethod
    def create_from_tree(cls, tree):
        binary_tree = cls()

        root = tree.root
        if root is not None:
            root = BinaryTreeNode.create_from_tree_node(root)
        binary_tree.root = root

        return binary_tree

class BinaryCousinTree(BinaryTree):
    @classmethod
    def create_from_binary_tree(cls, binary_tree):
        binary_cousin_tree = cls()

        root = binary_tree.root
        if root is not None:
            root = BinaryCousinTreeNode.create_from_binary_tree_node(root)
        binary_cousin_tree.root = root

        return binary_cousin_tree

class BinarySearchTree(BinaryTree):
    def put(self, value):
        if self.root:
            self.root.put(value)
        else:
            self.root = BinarySearchTreeNode(value)

    def search(self, value):
        if self.root:
            return self.root.search(value)
        return None

a = TreeNode(5)
b = TreeNode(11)
c = TreeNode(4)
d = TreeNode(2)
e = TreeNode(6, [a, b])
f = TreeNode(9, [c])
g = TreeNode(7, [d, e])
h = TreeNode(5, [None, f])
i = TreeNode(2, [g, h])

tree = Tree.create_from_root(i)

print("Tree")
print(tree)

print()
print("BFT")
tree.breadth_first_traverse()

print()
print("BFS: True, None")
print(tree.breadth_first_search(5) is h)
print(tree.breadth_first_search(-1))

print()
print("DFT")
tree.depth_first_traverse()

print()
print("DFS: True, None")
print(tree.depth_first_search(5) is a)
print(tree.depth_first_search(-1))

binary_tree = BinaryTree.create_from_tree(tree)

print()
print("Tree to BT")
print(binary_tree)

print()
print("Tree to BT is BST: False")
print(binary_tree.is_binary_search_tree())

a = BinarySearchTreeNode(4)
b = BinarySearchTreeNode(7)
c = BinarySearchTreeNode(13)
d = BinarySearchTreeNode(1)
e = BinarySearchTreeNode(6, a, b)
f = BinarySearchTreeNode(14, c)
g = BinarySearchTreeNode(3, d, e)
h = BinarySearchTreeNode(10, None, f)
i = BinarySearchTreeNode(8, g, h)

binary_search_tree = BinarySearchTree.create_from_root(i)

print()
print("BST")
print(binary_search_tree)

print()
print("BST search: True, None")
print(binary_search_tree.search(13) is c)
print(binary_search_tree.search(-1))

print()
print("is BST: True")
print(binary_search_tree.is_binary_search_tree())

binary_search_tree = BinarySearchTree()
binary_search_tree.put(8)
binary_search_tree.put(3)
binary_search_tree.put(10)
binary_search_tree.put(1)
binary_search_tree.put(6)
binary_search_tree.put(14)
binary_search_tree.put(4)
binary_search_tree.put(7)
binary_search_tree.put(13)

print()
print("BST put")
print(binary_search_tree)

print()
print("is BST: True")
print(binary_search_tree.is_binary_search_tree())

binary_search_tree = BinarySearchTree()
binary_search_tree.put('dog')
binary_search_tree.put('cat')
binary_search_tree.put('bear')
binary_search_tree.put('fish')
binary_search_tree.put('turtle')
binary_search_tree.put('cow')
binary_search_tree.put('pig')
binary_search_tree.put('rat')
binary_search_tree.put('lizard')

#          'dog'
#           / \
#      'cat'   'fish'
#       / \        \
# 'bear'   'cow'    'turtle'
#                     /
#                'pig'
#                 / \
#         'lizard'   'rat'

print()
print("BST")
print(binary_search_tree)

print()
print("is BST: True")
print(binary_search_tree.is_binary_search_tree())

binary_cousin_tree = (
    BinaryCousinTree.create_from_binary_tree(binary_search_tree)
)

print()
print("BST to BCT")
print(binary_cousin_tree)

print()
print("BST to BCT is BST: True")
print(binary_cousin_tree.is_binary_search_tree())

def find_prime(n):
    count = 0
    prime = 2
    i = 3
    while count < n:
        if is_prime(i):
            count += 1
            prime = i
        i += 1
    return prime

def find_prime_do_while(n):
    count = None
    prime = None
    i = 0
    while True:
        if is_prime(i):
            if count is None:
                count = 0
            else:
                count += 1
            prime = i
        i += 1
        if count == n:
            return prime

def is_prime(number):
    if (number <= 1):
        return False
    elif (number <= 2):
        return True
    elif number % 2 == 0:
        return False

    i = 3
    while ((i**2) <= number):
        if number % i == 0:
            return False
        i += 2
    return True

print()
print("primes")
print(find_prime(0))
print(find_prime(1))
print(find_prime(2))
print(find_prime(3))
print(find_prime(4))
print(find_prime(5))
print(find_prime(6))