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

    # Fügt rekursiv ein neues Element mit dem Wert value in den Baum ein
    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)

    # Methode zur Darstellung des Baums
    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)

    # Sucht ein Element mit dem Wert value im Baum
    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)

    # Zählt die Anzahl der Elemente im Baum
    def count(self):
        count = 1
        if self.left is not None:
            count += self.left.count()
        if self.right is not None:
            count += self.right.count()
        return count

    # Löscht ein Element mit dem Wert value aus dem Baum
    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

    # Gibt die Elemente des Baums in einer Liste (preorder) aus
    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

    # Sucht das kleinste Element im Baum
    def min(self):
        if self.left is not None:
            return self.left.min()
        else:
            return self.value


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

    # Fügt rekursiv ein neues Element mit dem Wert value in den Baum ein
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            return self.root.insert(value)

    # Methode zur Darstellung des Baums
    def show(self):
        if self.root is not None:
            self.root.show(0)
        else:
            print("Baum ist leer")

    # Sucht ein Element mit dem Wert value im Baum
    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")

    # Zählt die Anzahl der Elemente im Baum
    def count(self):
        if self.root is not None:
            print(f"Anzahl Knoten: {self.root.count()}")
        else:
            print("Anzahl Knoten: 0")

    # Löscht ein Element mit dem Wert value aus dem Baum
    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.")

    # Gibt die Elemente des Baums in einer Liste (preorder) aus
    def treeToList(self):
        output = []
        if self.root is not None:
            return self.root.treeToList(output)
        else:
            return []

    # Erzeugt rekursiv einen neuen Baum aus den Elementen einer Liste
    def createTree(self, list):
        if list:
            mid = len(list)//2
            self.insert(list[mid])
            self.createTree(list[:mid])
            self.createTree(list[mid+1:])

    # Sucht das kleinste Element im Baum
    def min(self):
        if self.root is not None:
            return print(f"Kleinstes Element: {self.root.min()}")
        else:
            return print("Kleinstes Element: Baum ist leer")

b = Tree()
b.insert(4)
b.insert(7)
b.insert(2)
b.insert(8)
b.insert(3)
b.insert(1)
print(b.treeToList())