#include <iostream>

using namespace std;

struct Cvor {
    Cvor(int n):vrednost(n){};
    int vrednost;
    Cvor *levo = nullptr;
    Cvor *desno = nullptr;
};

/* ---- Pomocne funkcije ------- */

Cvor* dodaj_u_stablo(Cvor *koren, int n)
{
    if(koren == nullptr)
        return new Cvor(n);
    
    if(n <= koren->vrednost)
        koren->levo = dodaj_u_stablo(koren->levo, n);
    else
        koren->desno = dodaj_u_stablo(koren->desno, n);
    
    return koren;
}

void LKD(Cvor *koren)
{
    if(koren != nullptr)
    {
        LKD(koren->levo);
        cout << koren->vrednost << " ";
        LKD(koren->desno);
    }
}

void oslobodi(Cvor *koren)
{
    if(koren != nullptr)
    {
        oslobodi(koren->levo);
        oslobodi(koren->desno);
        delete koren;
    }
}

/*---------------------*/


int najveci(Cvor *koren)
{
    if(koren == nullptr)
        return -1;
    
    if(koren->desno != nullptr)
        return najveci(koren->desno);
    else
        return koren->vrednost;
}

Cvor* brisanje(Cvor *koren, int broj)
{
    if(koren == nullptr)
        return koren;
    
    if(broj < koren->vrednost)
    {
        koren->levo = brisanje(koren->levo, broj);
        return koren;
    }
    else if (broj > koren->vrednost)
    {
        koren->desno = brisanje(koren->desno, broj);
        return koren;
    }
    
    // Cvor je list
    if(koren->levo == nullptr && koren->desno == nullptr)
    {
        delete koren;
        return nullptr;
    }
    
    // Cvor ima samo levog sina
    if(koren->desno == nullptr)
    {
        Cvor *tmp = koren->levo;
        delete koren;
        return tmp;
    }
    
    // Cvor ima samo desnog sina
    if(koren->levo == nullptr)
    {
        Cvor *tmp = koren->desno;
        delete koren;
        return tmp;
    }
    
    // Cvor ima oba sina
    int max = najveci(koren->levo);
    koren->vrednost = max;
    koren->levo = brisanje(koren->levo, max);
    return koren;
}

int main()
{
    Cvor *koren = nullptr;
    
    koren = dodaj_u_stablo(koren, 4);
    koren = dodaj_u_stablo(koren, 1);
    koren = dodaj_u_stablo(koren, 3);
    koren = dodaj_u_stablo(koren, 5);
    koren = dodaj_u_stablo(koren, 7);
 
    LKD(koren);
    
    koren = brisanje(koren, 4);
    cout << endl;
    
    LKD(koren);
    
    oslobodi(koren);
    
    return 0;
}