#include<iostream>
using namespace std;

struct element{
       int vrijednost;
       element *lijevo,*desno;
};
typedef struct element bstablo;

void InitB(int x, bstablo *B){
     B->vrijednost=x;
     B->lijevo=NULL;
     B->desno=NULL;
};

element *ParentB(int n, bstablo *B){
        if(n==B->vrijednost) cout<<"Cvor je korijen"<<endl;
        else{
             element *roditelj=NULL;
             if(B->lijevo){
                              if(B->lijevo->vrijednost==n) return B;
                              roditelj=ParentB(n,B->lijevo);
                              }
             if(B->desno){
                               if(B->desno->vrijednost==n) return B;
                               roditelj=ParentB(n,B->desno);
                               }
             return roditelj;
             }
}
element *trazi(int n, bstablo *B) {
        bstablo *tekuci,*tekuci2;
        tekuci=B;
        while(tekuci){
                      if(tekuci->vrijednost==n)return tekuci;
                      else tekuci=tekuci->desno;
                      }
        tekuci2=B;
        while(tekuci2){
                      if(tekuci2->vrijednost==n) return tekuci2;
                      else tekuci2=tekuci2->lijevo;
                      }
        cout<<"Nije naden nijedan cvor"<<endl;
        bstablo *zadnji;
        zadnji=B;
        while(zadnji->lijevo){
                      zadnji=zadnji->lijevo;
                      }
        return zadnji;       
}

element *LeftChildB(int n,bstablo *B){
        bstablo *novo=B;
        element *novi=trazi(n,novo);
        if(novi->lijevo==NULL){
                               novi->vrijednost=-1;
                               return novi;
        }
        else{
             novi=novi->lijevo;
             return novi;
        }
       
}
element *RightChildB(int n, bstablo *B){
        bstablo *novo=B;
        element *novi=trazi(n,novo);
        if(novi->desno==NULL){
                               novi->vrijednost=-1;
                               return novi;
        }
        else{
             novi=novi->desno;
             return novi;
        }
}
int LabelB(int n, bstablo *B){
    bstablo *novo=B;
    element *novi=trazi(n,novo);
    return novi->vrijednost;
}
void ChangeLabelB(int x, int n, bstablo *B){
     bstablo *novo=B;
     element *novi=trazi(n,novo);
     novi->vrijednost=x;
}
element *RootB(bstablo *B){
        element *novi=new element;
        novi->vrijednost=B->vrijednost;
        return novi;
}
void CreateLeftB(int x,int n, bstablo *B){
     bstablo *novo=B;
     element *cvor=trazi(n,novo);
     if(cvor->lijevo==NULL){
                            element *novi=new element;
                            novi->lijevo=NULL;
                            novi->desno=NULL;
                            novi->vrijednost=x;
                            cvor->lijevo=novi;
                            }
     else{
          cout<<"Taj cvor vec ima lijevo dijete!!!"<<endl;
     }
}
void CreateRightB(int x,int n, bstablo *B){
     bstablo *novo=B;
     element *cvor=trazi(n,novo);
     if(cvor->desno==NULL){
                            element *novi=new element;
                            novi->lijevo=NULL;
                            novi->desno=NULL;
                            novi->vrijednost=x;
                            cvor->desno=novi;
                            }
     else{
          cout<<"Taj cvor vec ima desno dijete!!!"<<endl;
     }
}
void DeleteB(element *n, bstablo *B){
     static bool brisanje=true;
     if(brisanje) {
                   element *roditelj=ParentB(n->vrijednost,B);
                   if(roditelj->lijevo==n) roditelj->lijevo=NULL;
                   else roditelj->desno=NULL;
                   brisanje=false;
                 }
     if(n->lijevo)DeleteB(n->lijevo,B);
     if(n->desno)DeleteB(n->desno,B);
     delete n;
}