from queue import Queue
from stack import Stack

class Node:
    def __init__(self, value):
        self.value = value  # Wert des Knotens
        self.left = None    # Linkes Kind
        self.right = None   # Rechtes Kind

    def insert(self, value):
        if self.value == value:
            return print("Die Daten existieren schon.")
        else:
            if self.value > value:
                if self.left is not None:
                    return self.left.insert(value)
                else:
                    self.left = Node(value)
            else:
                if self.right is not None:
                    return self.right.insert(value)
                else:
                    self.right = Node(value)

    def show(self, level):
        if self.left is not None:
            self.left.show(level + 1)
        print(' ' * 4 * level + "->" + str(self.value))
        if self.right is not None:
            self.right.show(level + 1)

    def search(self, value):
        if self.value == value:
            return True
        elif self.value > value:
            if self.left is not None:
                return self.left.search(value)
        else:
            if self.right is not None:
                return self.right.search(value)

    def delete(self, value):
        if value < self.value:
            if self.left is not None:
                self.left = self.left.delete(value)
        elif value > self.value:
            if self.right is not None:
                self.right = self.right.delete(value)
        else:
            if self.left is None:
                return self.right
            elif self.right is None:
                return self.left
            else:
                min_larger_node = self.right
                while min_larger_node.left is not None:
                    min_larger_node = min_larger_node.left
                self.value = min_larger_node.value
                self.right = self.right.delete(min_larger_node.value)
        return self

    def treeToList(self, output):
        output.append(self.value)
        if self.left is not None:
            self.left.treeToList(output)
        if self.right is not None:
            self.right.treeToList(output)
        return output


class Tree:
    def __init__(self):
        self.root = None  # Wurzel des Baums

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            return self.root.insert(value)

    def show(self):
        if self.root is not None:
            self.root.show(0)
        else:
            print("Baum ist leer")

    def search(self, value):
        if self.root is not None:
            print(f"gesuchter Knoten: {self.root.search(value)}")
        else:
            print("gesuchter Knoten: Baum ist leer")

    def delete(self, value):
        if self.root is not None:
            self.root = self.root.delete(value)
        else:
            print("Baum ist leer, nichts zu löschen.")

    def treeToList(self):
        output = []
        if self.root is not None:
            return self.root.treeToList(output)
        else:
            return []