#include <assert.h>

struct UzelStromu {
    int data;

    UzelStromu *levy, *pravy;

    UzelStromu(const int hodnota) {
        data = hodnota;
        levy = NULL;
        pravy = NULL;
    }
};

struct BinarniStrom {
    UzelStromu *koren;

    BinarniStrom() {
        koren = NULL;
    }

    bool pridejPrvek(const int hodnota);

    bool najdiPrvek(const int hodnota);

    void smazPrvek(const int hodnota);

    ~BinarniStrom();


    /****
     * Pomocne metody
     */
protected:


    bool hledejPrvek(const UzelStromu* podstrom,
            const int hodnota,
            UzelStromu** predchudce,
            UzelStromu** prvek);
    
    void smazPodstrom( UzelStromu* podstrom );
    
    void smazList( UzelStromu* prvek, UzelStromu* predchudce );
    
    void smazVeVetvi( UzelStromu* prvek, UzelStromu* predchudce );

};

bool BinarniStrom::hledejPrvek( UzelStromu* podstrom,
                                const int hodnota,
                                UzelStromu** predchudce,
                                UzelStromu** prvek)
{
    if (podstrom != NULL)
    {        
        if (podstrom->data == hodnota)
        {
            (*prvek) = podstrom;
            return true;
        }
        (*predchudce)=podstrom;
        if (podstrom->data < hodnota)
            return hledejPrvek(podstrom->levy, hodnota, predchudce, prvek);
        else
            return hledejPrvek(podstrom->pravy, hodnota, predchudce, prvek);
    }    
    *prvek = NULL;
    return false;
}

bool BinarniStrom::pridejPrvek(const int hodnota) {
    if (koren == NULL) {
        koren = new UzelStromu(hodnota);
        return true;
    }
    UzelStromu * predchudce, *prvek;
    if (hledejPrvek(koren, hodnota, &predchudce, &prvek))
        return false;
    if (predchudce->data<hodnota)
        predchudce->pravy=new UzelStromu(hodnota);
    else
       predchudce->levy= new UzelStromu(hodnota);
    return true;
}

bool BinarniStrom::najdiPrvek(const int hodnota)
{
    UzelStromu *predchudce, *prvek;
    return hledejPrvek(koren, hodnota, &predchudce, &prvek);
}

void BinarniStrom::smazPodstrom( UzelStromu* podstrom )
{
    if(podstrom->levy!=NULL){
        smazPodstrom(podstrom->levy);}
    if(podstrom->pravy!=NULL){
        smazPodstrom(podstrom->pravy);}
    delete podstrom;
}

BinarniStrom::~BinarniStrom()
{
    if( koren != NULL ) smazPodstrom( koren );
}

bool BinarniStrom::smazPrvek(const int hodnota)
{
    
    UzelStromu *predchudce, *prvek;
    predchudce = NULL;
    prvek = NULL;
    
    if(hledejPrvek(koren, hodnota, &predchudce, &prvek)==false) 
    {
        return false;
    }
    
    if ( prvek->pravy == NULL && prvek->levy == NULL) 
    {
        smazList(predchudce, prvek);
        return true;
    }
    
    if ( prvek->pravy != NULL && prvek->levy != NULL)
    {
        smazVeStromu(prvek, predchudce);
        return true;
    }
    
    smazVeVetvi(prvek, predchudce);
    return true;   
}