#include <cstdio>
#include <cstdlib>
FILE*fi,*fout;
struct Nod{
   Nod *fiust;
   Nod *fiudr;
   int val;
   int dim;
   int sum;
};
struct Pereche{
   Nod *primul;
   Nod *aldoilea;
};
Nod *gol=new Nod{nullptr,nullptr,0,0,0};

Nod *creeaza_nod(int val){
    return new Nod{gol,gol,val,1,val};
}

Nod *creeaza_nod(Nod *rad,Nod *fiust,Nod *fiudr){
    return new Nod{fiust,fiudr,rad->val,fiust->dim+1+fiudr->dim,fiust->sum+rad->val+fiudr->sum};
}

Nod *modifica_nod(Nod *rad,Nod *fiust,Nod *fiudr){
    *rad=Nod{fiust,fiudr,rad->val,fiust->dim+1+fiudr->dim,fiust->sum+rad->val+fiudr->sum};
    return rad;
}

char exista(Nod *rad,int val){
    if(rad==gol)
         return 0;
    else if(rad->val==val)
        return 1;
    else if(rad->val<val)
        return exista(rad->fiudr,val);
    else // if(rad->val>val)
        return exista(rad->fiust,val);
}
Nod *adauga(Nod *rad,int val){
    if(rad==gol)
        return creeaza_nod(val);
    else if(rad->val==val)
        return rad;
    else if(rad->val<val)
        return creeaza_nod(rad,rad->fiust,adauga(rad->fiudr,val));
    else // if(rad->val>val)
        return creeaza_nod(rad,adauga(rad->fiust,val),rad->fiudr);
}
struct Pereche desparte(Nod *rad,int val){
    if (rad==gol)
        return Pereche{gol,gol};
    else if(rad->val>val) {
        Pereche p = desparte(rad->fiust,val);
        return Pereche{
            p.primul,
            creeaza_nod(rad,p.aldoilea,rad->fiudr)
        };
    }else{
        Pereche p = desparte(rad->fiudr,val);
        return Pereche{
           creeaza_nod(rad,rad->fiust,p.primul),
           p.aldoilea
        };
    }
};
Nod *uneste(Nod *unu,Nod *doi){
    if (unu==gol)
        return doi;
    else if(doi==gol)
        return unu;
    else if(rand() % 2)
        return creeaza_nod(unu,unu->fiust,uneste(unu->fiudr,doi));
    else
        return creeaza_nod(doi,uneste(unu,doi->fiust),doi->fiudr);
};
Nod *sterge(Nod *rad,int val){
    if(rad==gol)
        return rad;
    else if(rad->val==val)
        return uneste(rad->fiust,rad->fiudr);
    else if(rad->val<val)
        return creeaza_nod(rad,rad->fiust,sterge(rad->fiudr,val));
    else
        return creeaza_nod(rad,sterge(rad->fiust,val),rad->fiudr);
}
int elementul_N(Nod *rad,int n){
    if(rad->fiust->dim==n)
        return rad->val;
    else if(rad->fiust->dim>n)
        return elementul_N(rad->fiust,n);
    else
        return elementul_N(rad->fiudr,n-rad->fiust->dim-1);
}
void afiseaza(Nod *rad,int adancime=0){
    if(rad!=gol) {
        afiseaza(rad->fiust,adancime+1);
        for(int i = 0; i < adancime; i++){
            fprintf(fout, " ");
        }
        fprintf(fout,"%d\t%d\t%d\n" ,rad->val,rad->dim,rad->sum);
        afiseaza(rad->fiudr,adancime+1);
    }
}
int main(){
    fi=fopen("BST.in" ,"r");
    fout=fopen("BST.out" ,"w");

    Nod* n = gol;
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = adauga(n, 6);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = adauga(n, 5);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = adauga(n, 3);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = adauga(n, 7);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = adauga(n, 2);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = adauga(n, 8);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = adauga(n, 4);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");
    n = sterge(n, 6);
    afiseaza(n);
    fflush(fout);
    fprintf(fout,"\n");

    fclose(fi);
    fclose(fout);
    return 0;
}