class Node:

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

    def set_left(self, node):
        self.left = node

    def set_right(self, node):
        self.right = node

    def set_value(self, value):
        self.value = value

    def get_left(self):
        return self.left

    def get_right(self):
        return self.right

    def get_value(self):
        return self.value


class Tree:

    def __init__(self):
        self.root = None

    def insert(self, root, value):

        node = Node(value)

        if self.root is None:
            self.root = node
            return True

        if value <= root.get_value():
            if root.get_left():
                return self.insert(root.get_left(), value)
            return root.set_left(node)

        if value > root.get_value():
            if root.get_right():
                return self.insert(root.get_right(), value)
            return root.set_right(node)

    def print(self, root):
        if self.root is None:
            return False
        if root.get_left():
            self.print(root.get_left())
        if root.get_value():
            print(root.get_value())
        if root.get_right():
            self.print(root.get_right())

    def get_root(self):
        return self.root

    def search(self, root, value):

        if root is not None:
            if value == root.get_value():
                return root
            if value < root.get_value():
                return self.search(root.get_left(), value)
            if value > root.get_value():
                return self.search(root.get_right(), value)

        else:
            return False

    def maximum(self, root):

        if root.get_right():
            return self.maximum(root.get_right())
        return root

    def minimum(self, root):

        if root.get_left():
            return self.minimum(root.get_left())
        return root

    def predecessor(self, root, value):

        root = self.search(root, value)
        if root:
            if root.get_left():
                return self.maximum(root.get_left())
        return False

    def successor(self, root, value):

        root = self.search(root, value)
        if root:
            if root.get_right():
                return self.minimum(root.get_right())
        return False

    def get_dad(self, root, value):
        if root is not None:
            if (root.get_left() and root.get_left().get_value() == value) or (root.get_right() and root.get_right().get_value() == value):
                return root
            elif root.get_left() and value < root.get_value():
                return self.get_dad(root.get_left(), value)
            elif root.get_right() and value > root.get_value():
                return self.get_dad(root.get_right())
        return False

    def delete(self, root, value):

        if root is None:
            return False

        el = self.search(root, value)

        if el:
            if el.get_right():
                successor = self.successor(root, value)
                self.get_dad(el, successor.get_value()).set_right(None)
                el.value = successor.get_value()
            elif el.get_left():
                predecessor = self.predecessor(root, value)
                self.get_dad(el, predecessor.get_value()).set_left(None)
                el.value = predecessor.get_value()
            elif el.get_right() is None and el.get_left():
                dad = el.get_dad()
                if el.get_value() > dad.get_value():
                    dad.set_right(None)
                else:
                    dad.set_left(None)
            return True
        return False


if __name__ == '__main__':

    tree = Tree()
    tree.insert(tree.root, 10)
    tree.insert(tree.root, 8)
    tree.insert(tree.root, 15)
    tree.insert(tree.root, 5)
    tree.insert(tree.root, 2)
    tree.insert(tree.root, 6)
    tree.delete(tree.get_root(), 8)
    tree.print(tree.get_root())