5_1

/*
Zur Abgabe einen branch `iprg-b05` erstellen und pushen, in dem als einzige Datei die `05ex.c` liegt.
*/

/*
Um die Tests für dieses Blatt zu kompilieren und zu starten, führen Sie den folgenden Befehl aus:
cc -std=c11 -g -Wall -Werror 05ex_test.c -o 05ex_test.o -lm && ./05ex_test.o

Wir empfehlen, mit möglichst streng eingestelltem valgrind zu testen, denn so testen wir auch auf dem Server:
cc -std=c11 -g -Wall -Werror 05ex_test.c -o 05ex_test.o -lm && valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes ./05ex_test.o
*/

#include "search_tree.h"
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

/*
Aufgabe 1:

Fügen Sie den Wert `x` als Blatt so in den nicht-leeren Suchbaum `t` ein, dass `t` hinterher
wieder ein Suchbaum ist. Falls `x` bereits in `t` vorkam, soll `t` stattdessen
unverändert bleiben.
Geben Sie zurück, ob der Baum modifiziert wurde.

Nutzen Sie `malloc`, um das neue Blatt zu erstellen. Der Testrunner wird das Blatt wieder `free`n,
darum brauchen Sie sich nicht zu kümmern.
*/
bool search_tree_insert(TreeNode *t, uint16_t x) {

    if(t==NULL) return false;

    TreeNode *current = NULL;
    TreeNode *next = t;
    TreeNode *new_elem = (TreeNode *)malloc(sizeof(TreeNode));

    new_elem->item = x;
    new_elem->left = NULL;
    new_elem->right = NULL;

    while (next){
        current = next;
        if(next->item < x){ //suchen den linken teilbaum ab
            next = next->left;
        }
        else if(next->item > x){ //suchen den rechten teilbaum ab
            next = next->right;
        }
        else{ // item = x also element schon im baum vorhanden
            return false; //nicht eingefuegt also nicht geaendert
        }
    } // haben den platz fuer x gefunden

    if(x <= current->item){
        current->left = new_elem;
    }
    else{
        current->right = new_elem;
    }
    //free(new_elem);
    return true;
}

/*
Aufgabe 2:
Geben Sie die kleinste Zahl im Suchbaum `t` zurück, welche echt größer als `x` ist.
Falls keine solche Zahl existiert, geben Sie stattdessen `x` zurück. Die Laufzeit Ihrer Lösung soll
proportional zur Höhe des Baumes sein, aber unabhängig von der Gesamtzahl an Knoten.
*/
/*uint16_t find_min(TreeNode *t){

    TreeNode *leaf = t;
    if(leaf->left){ //es gibt ein kleineren elem
        //find_min(leaf->left);
    }
    else if(leaf->right){
        find_min(leaf->right);

    return leaf->item;
}
*/

uint16_t search_tree_get_greater_than(TreeNode *t, uint16_t x) {

    TreeNode *leaf = t;
    int res;
    //int min_item = find_min(t);
    //if(min_item > x) return min_item;

    while(leaf){ //baum durchsuchen
        if(leaf->item <= x){ //schauen im rechten teilbaum, weil wir eine groessere zahl suchen
            leaf = leaf->right;
        }
        else{ //item groesser als x, koennte entweder unsere antwort sein oder es gibt eine kleinere zahl
            leaf = leaf->left;
            res = leaf->item;
        }
    }

    if (res) return res; // wenn res gefunden (ohne dass NULL zeiger am ende des baums erreicht wurde), ist sein item unsere gesuchte zahl
    else return x; // nichts gefunden, x zurueckgeben

}