import random


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


def insert_to_bst(root, node, height):
    if node.value <= root.value:
        if root.left is None:
            root.left = node
            return height + 1
        else:
            height = insert_to_bst(root.left, node, height + 1)
    else:
        if root.right is None:
            root.right = node
            return height + 1
        else:
            height = insert_to_bst(root.right, node, height + 1)
    return height


def build_bst(elements):
    root = Node(elements[0])
    max_height = 0
    for i in range(1, len(elements)):
        height = 0
        height = insert_to_bst(root, Node(elements[i]), height)
        if height > max_height:
            max_height = height
    return root, max_height


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


def bst_max(node):
    print(node.value)
    if node.right is None:
        return node.value
    else:
        return bst_max(node.right)


def delete_node(node, number):
    if not node:
        return node
    elif node.value == number:
        if not node.right:
            return node.left
        if not node.left:
            return node.right
        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)
    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 delete_nodes(node, elements):
    for element in elements:
        delete_node(node, element)


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 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


sequence_type = None
while sequence_type != '0':
    print("-----------------------")
    print("1.Podaj wlasny ciag")
    print("2.Wygeneruj losowy ciag")
    print("0.Wyjscie")
    print("-----------------------")
    sequence_type = input(">")
    if sequence_type == '1':
        print("Podaj ciag oddzielajac liczby spacjami(np. \"1 2 3\"). Ciag moze miec maksymalnie 10 elementów.")
        try:
            numbers = [int(x) for x in input('>').split()]
            if len(numbers) not in range(1, 11):
                print("Nieodpowiednia liczba elementow!")
                sequence_type = None
        except Exception:
            print("Wystapil blad! Niepoprawny format danych.")
            sequence_type = None
    elif sequence_type == '2':
        # TODO moze dodam wiecej opcji(przedzial, wielkosc)
        numbers = [random.randint(1, 30) for x in range(0, 10)]
    if sequence_type in ['1', '2']:
        option = None
        tree_built = False
        while option != '0':
            print("--------------------------------------------------------------")
            print("1.Konstruuj nowe drzewo AVL metoda polowienia binarnego")
            print("2.Konstruuj nowe drzewo BST wstawiajac elementy ciagu po kolei")
            print("3.Znajdz minimum i maksimum oraz wypisz sciezke poszukiwania")
            print("4.Usun elementy o podanych wartosciach")
            print("5.Wypisz elementy drzewa w porzadkach in-order i pre-order")
            print("6.Usun cale drzewo metoda post-order")
            print("7.Zrownowaz drzewo przez rotacje")
            print("0.Wyjscie")
            print("--------------------------------------------------------------")
            option = input(">")
            if option == '1':
                # TODO dodac budowanie drzewa AVL
                pass
                tree_built = True
            elif option == '2':
                tree_root, tree_height = build_bst(numbers)
                print("Operacja zostala wykonana. Wysokosc drzewa:", tree_height)
                input("Wcisnij enter aby kontynuowac...")
                tree_built = True
            if tree_built:
                if option == '3':
                    print("Sciezka do minimum:")
                    minimum = bst_min(tree_root)
                    print("Sciezka do maksimum:")
                    maximum = bst_max(tree_root)
                    print("Minimum: {}, Maksimum: {}".format(minimum, maximum))
                    input("Wcisnij enter aby kontynuowac...")
                elif option == '4':
                    # TODO sprawdzic jak dziala gdy wystepuja duplikaty
                    print("Podaj liczby do usuniecia oddzielajac je spacjami(np. \"1 2 3\"):")
                    try:
                        to_delete = [int(x) for x in input(">").split()]
                        delete_nodes(tree_root, to_delete)
                    except Exception:
                        print("Wystapil blad! Niepoprawny format danych.")
                elif option == '5':
                    print("In-order:")
                    print_in_order(tree_root)
                    print("Pre-order")
                    print_pre_order(tree_root)
                    input("Wcisnij enter aby kontynuowac...")
                elif option == '6':
                    delete_tree(tree_root)
                elif option == '7':
                    # TODO dodac rownowazenie drzewa
                    pass
            else:
                print("--------------------------------------------------------------")
                print("Przed skorzystaniem z opcji 3-7 nalezy zbudowac drzewo!")