// Generische Klasse für einen Binären Suchbaum
class BinaererSuchbaum<T extends Comparable<T>> {
    // Knoten-Klasse
    private static class Knoten<T> {
        T daten;
        Knoten<T> links, rechts;

        Knoten(T daten) {
            this.daten = daten;
            links = rechts = null;
        }
    }

    private Knoten<T> wurzel;

    // Methode zum Hinzufügen von Elementen
    public void hinzufuegen(T wert) {
        this.wurzel = hinzufuegen(wert, wurzel);    
    }

    private Knoten<T> hinzufuegen(T wert, Knoten<T> wurzel) {
        if (wert != null)
            if (wurzel == null)
                wurzel = new Knoten<T>(wert);
            else
                if (wert.compareTo(wurzel.daten) < 0)
                    wurzel.links = hinzufuegen(wert, wurzel.links);
                else if (wert.compareTo(wurzel.daten) > 0)
                    wurzel.rechts = hinzufuegen(wert, wurzel.rechts);

        return wurzel;
    }

    // Methode zur Suche eines Elements
    public T suchen(T wert) {
        return suchen(wert, wurzel);
    }

    private T suchen(T wert, Knoten<T> wurzel) {
        if (wurzel == null || wert == null)
            return null;
        else
            if (wert.compareTo(wurzel.daten) < 0)
                return suchen(wert, wurzel.links);
            else if (wert.compareTo(wurzel.daten) > 0)
                return suchen(wert, wurzel.rechts);
            else if (wert.compareTo(wurzel.daten) == 0)
                return wurzel.daten;
            else
                return null;
    }


    // Methode zum Löschen eines Elements
    public void loeschen(T wert) {
        this.wurzel = loeschen(wert, wurzel);
    }

    private Knoten<T> loeschen(T wert, Knoten<T> wurzel) {
        if (wurzel != null && wert != null)
            if (wert.compareTo(wurzel.daten) < 0)
                wurzel.links = loeschen(wert, wurzel.links);
            else if (wert.compareTo(wurzel.daten) > 0)
                wurzel.rechts = loeschen(wert, wurzel.rechts);
            else if (wurzel.links == null)
                if (wurzel.rechts == null)
                    wurzel = null;
                else
                    wurzel = wurzel.rechts;
            else
                if (wurzel.rechts == null)
                    wurzel = wurzel.links;
                else {
                    Knoten<T> minInhalt = blattSuchen(wurzel, false);
                    minInhalt.links = wurzel.links;
                    wurzel = minInhalt;
                    wurzel.rechts = loeschen(minInhalt.daten, wurzel.rechts);
                }

        return wurzel;
    }

    public Knoten<T> blattSuchen(Knoten<T> wurzel, boolean links) {
        if (wurzel.daten == null)
            return null;
        else
            if (links)
                if (wurzel.links == null)
                    return wurzel;
                else
                    return blattSuchen(wurzel.links, links);
            else
                if (wurzel.rechts == null)
                    return wurzel;
                else
                    return blattSuchen(wurzel.rechts, links);
    }

    // Inorder-Traversierung für Ausgabe
    public void inorderAusgabe() {
        inorderRekursiv(wurzel);
        System.out.println();
    }

    private void inorderRekursiv(Knoten<T> knoten) {
        if (knoten != null) {
            inorderRekursiv(knoten.links);
            System.out.print(knoten.daten + " ");
            inorderRekursiv(knoten.rechts);
        }
    }
}