from random import randint


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


def print_pre_order(node):
    print(node.value)
    if node.left is not None:
        print_pre_order(node.left)
    if node.right is not None:
        print_pre_order(node.right)


def print_in_order(node):
    if node.left is not None:
        print_in_order(node.left)
    print(node.value)
    if node.right is not None:
        print_in_order(node.right)


def insert_to_bst(root, node, height):
    # gdy wstawiana liczba jest mniejsza lub równa korzeniowi
    if node.value <= root.value:
        # gdy korzen nie ma lewego dziecka
        if root.left is None:
            # lewym dzieckiem staje sie wstawiana liczba
            root.left = node
            # wysokość zwiększa się o 1 i jest zwracana
            return height + 1
        else:
            # w przeciwnym razie wywolaj funkcje wstawiajaca dla lewego dziecka jako korzen
            # przesuwamy sie w dół drzewa wiec wysokość zwiększa się o 1
            height = insert_to_bst(root.left, node, height + 1)
    # gdy wstawiana liczba jest wieksza od korzenia
    else:
        # gdy korzen nie ma prawego dziecka
        if root.right is None:
            # prawym dzieckiem staje sie wstawiana liczba
            root.right = node
            # wysokość zwiększa się o 1 i jest zwracana
            return height + 1
        else:
            # w przeciwnym razie wywolaj funkcje wstawiajaca dla prawego dziecka jako korzen
            # przesuwamy sie w dół drzewa wiec wysokość zwiększa się o 1
            height = insert_to_bst(root.right, node, height + 1)
    # zwracamy wysokość drzewa
    return height


# minimum dla bst to po prostu skrajnie lewy lisc
def bst_min(node):
    # wypisz obecny wezel
    print(node.value)
    # jak wezel nie ma lewego dziecka to zwracana jest jego wartosc
    if node.left is None:
        return node.value
    # w przeciwnym razie wywolaj ta funkcje dla lewego dziecka
    else:
        return bst_min(node.left)


# dziala analogicznie do bst_min
def bst_max(node):
    print(node.value)
    if node.right is None:
        return node.value
    else:
        return bst_max(node.right)


def delete_tree(node):
    if node.left is not None:
        delete_tree(node.left)
    if node.right is not None:
        delete_tree(node.right)
    node.value = None


def bst_min_for_delete(node):
    if node.left is None:
        return node.value
    else:
        return bst_min_for_delete(node.left)


def delete_node(node, number):  # na starcie na wejsciu jako node podajemy root
    # funkcja wykonuje sie az node nie bedzie pusty (dlaczego tak jest wyjasnione pozniej)
    if not node:
        return node
    # opcja 1: znalezlismy liczbe do usuniecia
    elif node.value == number:
        # opcja 1.1: nie ma prawego - za usuniety dajemy lewy, a reszta jest okej, tylko trzeba ja przestawic
        if not node.right:
            return node.left
        # opcja 1.2: nie ma lewego - za usuniety dajemy prawy, a reszta jest okej, tylko trzeba ja przestawic
        if not node.left:
            return node.right
        # opcja 1.3: sa 2 dzieci - za usuniety dajemy prawy, bo jest wiekszy, ale trzeba poprzestawiac reszte
        # nalezy znalesc najmniejszy, bo mozna powiedziec, ze pole z nim zniknie (patrz pierwszy if), a reszta sie przestawi
        lowest_node = node.right
        while lowest_node.left:
            lowest_node = lowest_node.left
        node.value = lowest_node.value
        node.right = delete_node(node.right, node.value)
    # opcja 2: dalej szukamy liczby do usuniecia
    elif node.value > number:
        node.left = delete_node(node.left, number)
    elif node.value < number:
        node.right = delete_node(node.right, number)
    return node


def build_AVL(numbers, i, j):
    if i > j:
        return None
    mid = (i + j) // 2
    root = Node(numbers[mid])
    root.left = build_AVL(numbers, i, mid-1)
    root.right = build_AVL(numbers, mid + 1, j)
    return root

numbers = sorted([randint(0, 20) for x in range(0, 10)])
print(numbers)
tree_root = build_AVL(numbers, 0, len(numbers)-1)
print_in_order(tree_root)






# ustalamy wartosc dla korzenia
# tree_root = Node(randint(0, 20))
# losujemy pozostale numery
# numbers = [randint(0, 20) for x in range(0, 9)]
# max_height = 0
# for number in numbers:
#     tree_height = 0
#     #wstawiamy nowy wezel do drzewa, funkcja zwróci wysokość na ktorej wezel został wstawiony
#     tree_height = insert_to_bst(tree_root, Node(number), tree_height)
#     #porownojemy czy wysokosc jest najwieksza do tej pory
#     if tree_height > max_height:
#         #i ewentualnie podmieniamy
#         max_height = tree_height
# print("Ciąg:", [tree_root.value] + numbers)
# print("Wysokosc drzewa:", max_height)
# print("Sciezka do minimum:")
# bst_min(tree_root)
# print("Sciezka do maksimum:")
# bst_max(tree_root)
# print("Elementy w kolejnosci pre-order")
# print_pre_order(tree_root)
# print("Elementy w kolejnosci in-order")
# print_in_order(tree_root)
# #usuniecie drzewa
# delete_tree(tree_root)
# delete_node(tree_root, 7)
# print_in_order(tree_root)