from collections import deque


class Node:
    def __init__(self, value, lchild=None, rchild=None):
        self.value = value
        self.lchild = lchild
        self.rchild = rchild


class BT:
    def __init__(self, root=None):
        self.level = deque()
        self.root = root
        self.q = deque()

    def __find(self, item, parent):
        if not parent:
            return False

        if parent.value == item:
            return True

        if parent.value > item:
            return self.__find(item, parent.lchild)
        elif parent.value < item:
            return self.__find(item, parent.rchild)

    def find(self, item):
        return self.__find(item, self.root)

    def __contains__(self, item):
        return self.find(item)

    def __insert(self, val, parent):
        if val <= parent.value:
            if parent.lchild is None:
                parent.lchild = Node(val)
            else:
                self.__insert(val, parent.lchild)

        if val > parent.value:
            if parent.rchild is None:
                parent.rchild = Node(val)
            else:
                self.__insert(val, parent.rchild)

    def add(self, val):
        if self.root is None:
            self.root = Node(val)
        else:
            self.__insert(val, self.root)

        return self

    def traverse_depth(self, parent=None):
        if parent is None:
            self.q.clear()
            parent = self.root

        if parent is None:
            return

        if parent.lchild:
            self.traverse_depth(parent.lchild)

        # print(parent.value)
        self.q.append(parent)

        if parent.rchild:
            self.traverse_depth(parent.rchild)

    def traverse_breadth(self, parent=None):
        if not parent and self.root:
            self.q.clear()
            self.level.clear()
            parent = self.root
            self.level.append(parent)

        if parent is None:
            return

        current_node = self.level.popleft()

        while current_node:
            self.q.append(current_node)

            if current_node.lchild:
                self.level.append(current_node.lchild)
            if current_node.rchild:
                self.level.append(current_node.rchild)

            if len(self.level) > 0:
                current_node = self.level.popleft()
            else:
                current_node = None

    def print_traversal(self):
        for node in self.q:
            print(node.value)


# Example Data
#                        50
#          25                             75
#    12          37              63                 87
# 6     18    31       44     57     69         81     93


bt = BT()
bt.add(50).add(25).add(75).add(12).add(37).add(63) \
    .add(87).add(6).add(18).add(31).add(44).add(57) \
    .add(69).add(81).add(93)

print('DFS')
bt.traverse_depth()
bt.print_traversal()

print('BFS')
bt.traverse_breadth()
bt.print_traversal()

print('bsearch')
print(f'{63 in bt}')
print(f'{23 in bt}')
print(f'{93 in bt}')
print(f'{6 in bt}')
print(f'{45 in bt}')