05ex

/*
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) {
    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(x < next->item){ //suchen den linken teilbaum ab
            next = next->left;
        }
        else if(x > next->item){ //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;
    }
    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 search_tree_get_greater_than(TreeNode *t, uint16_t x) {

    uint16_t res = x;

    TreeNode *leaf = t;
    TreeNode *leaf_greater = NULL;

    while(leaf){ //baum durchsuchen
        //printf("leaf->item = %d\n", leaf->item);
        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_greater = leaf;
            leaf = leaf->left;
        }
    }

    if (leaf_greater) res =  leaf_greater->item; // wenn ein passendes blatt gefunden (ohne dass NULL zeiger am ende des baums erreicht wurde), ist sein item unsere gesuchte zahl

    return res;

}