/*
Schreiben bzw. vervollständigen Sie gekennzeichnete Programmteile wie in den Kommentaren beschrieben.
Verändern Sie aber nicht vorgegebene Methodenköpfe oder andere vorgegebene Programmteile!
Verwenden Sie die gegebenen Testklassen zum Überprüfen Ihrer Lösung. Die Korrektheit dieser Testfälle
ist notwendig, aber nicht hinreichend für eine korrekte Lösung. Es werden damit nur bestimmte
Spezialfälle geprüft. Liefern die Testklassen keinen Fehler, garantiert dies noch nicht die
Korrektheit Ihrer Lösung gemäß der Angabe.
*/

public class Aufgabe2 {

    /*
    Aufgabe:
        Objekte der Klasse Tree stellen binäre Suchbäume über ganzen Zahlen mit Knoten vom Typ Node dar.
        Ergänzen Sie fehlende Teile der Klassen entsprechend den Kommentaren an den mit TODO gekennzeichneten Stellen.
        Hinweis: Die Methode 'add' ist bereits vollständig vorgegeben.

    Punkte (maximal 20):
        12 Punkte für removeLeaves,
        8 Punkte für toString.
    */

    // Diese Methode können Sie zum Testen nutzen. Sie geht nicht in die Beurteilung ein.
    public static void main(String[] args) {

        Tree tree = new Tree();
        tree.add(5);
        tree.add(2);
        tree.add(7);
        tree.add(6);
        tree.add(8);
        tree.add(1);
        tree.add(1);
        tree.add(3);

        System.out.println(tree); //[1,1,2,3,5,6,7,8]
        System.out.println();

        tree.removeLeaves();

        System.out.println(tree); //[1,2,5,7]
        System.out.println();

        tree = new Tree();
        System.out.println(tree); //[]

    }
}

class Node {

    // Deklarieren Sie hier keine weiteren globalen/Objekt- Variablen.
    // Innerhalb der Methoden können lokale Variablen genutzt werden.

    // Den Konstruktor nicht verändern.
    public Node(int elem) {

    }

    // Rekursive Hilfsmethode für 'add' von 'Tree'.
    void add(int elem) {



    }

    // Rekursive Hilfsmethode für 'removeLeaves' von 'Tree'.
    // Hinweis: Der Rückgabewert (boolean) kann angeben,
    // ob ein Knoten ein Blattknoten ist und somit entfernt werden muss.
    boolean removeLeaves() {








        // TODO: Implementieren Sie die Methode.
        return false; //TODO: Diese Zeile löschen.
    }

    @Override
    // Rekursive Hilfsmethode für 'toString' von 'Tree'.
    public String toString() {



        // TODO: Implementieren Sie die Methode.
        return null; //TODO: Diese Zeile löschen.
    }
}

class Tree {
    // Der Wurzelknoten des Baumes. Bitte nicht verändern, oder zusätzliche
    // Variablen hinzufügen.
    private Node root;

    public boolean empty() {
        return false;
    }

    // Fügt neue Elemente in den Baum ein.
    // z.B. Die Aufrufe add(5),add(2),add(7),add(6),add(8),add(1),add(1),add(3)
    // ergeben folgenden Baum:
    //              5
    //           /    \
    //         7        2
    //       /   \     /  \
    //      8     6   3    1
    //                      \
    //                       1
    public void add(int elem) {

    }

    // Diese Methode entfernt alle Blätterknoten des Baumes. Wird die Methode
    // auf den oben gezeigten Baum angewendet, dann entsteht folgender Baum:
    //              5
    //           /    \
    //         7        2
    //                    \
    //                     1
    // Besteht der Baum nur aus dem Wurzelknoten, wird dieser gelöscht.
    public void removeLeaves(){

        // TODO: Implementieren Sie die Methode
    }

    // Retourniert alle Elemente des Baumes in aufsteigender Reihenfolge als
    // String.
    // z.B. der Baum enthält 1, 2, 3 and 4, dann ist das Ergebnis:
    // "[1,2,3,4]"
    // Für einen leeren Baum wird "[]" zurückgegeben.
    @Override
    public String toString() {
        // TODO: Implementieren Sie die Methode


        return ""; //TODO: Diese Zeile löschen.
    }

}