#include<iostream>
#include <cstring>
using namespace std;
 
struct element
{
	string label;
	struct element  *left, *right;
};
 
typedef element *node;
typedef element btree;
//vrati prvo lijevo dijete zadanog cvora
node LeftChildB(btree *stablo, node n)
{
	return n->left;
}
//vrati prvo desno dijete zadanog cvora
node RightChildB(btree *stablo, node n)
{
	return n->right;
}
//ispisi oznaku koja se nalazi na zadanom cvoru
void LabelB(btree *stablo, node n)
{
	cout<<"Oznaka na zadanome cvoru je : "<< n->label<<endl;
}
void ChangeLabelB(string nova_vrijednost,node cvor, btree *stablo) {
    if(cvor==NULL) 
    return;
    cout<<"Mijenjam vrijednost "<<cvor->label<<"\nu novu vrijednost: "<<nova_vrijednost<<endl; 
    cvor->label = nova_vrijednost;
}
//vrati korijen stabla
node RootB(btree *stablo)
{
	return stablo;
}
 
node ParentB(btree *stablo, node n) {
    if (n == stablo)//ako je cvor ==korijenu vrati 0 
    return NULL;
 
    node roditelj = NULL; //pom varijabla za roditelja
    if (stablo->left) {//ako trenutno stablo ima lijeve dijece idi lijevo
        if (stablo->left == n)
         return stablo; //ako je prvo lijevo dijete TRENUTNOG stabla jednako n vrati trenutni "korijen" stabla
        else
        roditelj =  ParentB(n, stablo->left);//ako nije pronadjen "roditelj" idi dublje u stablo rekurzijom
        }
        if(stablo->right) {//ako trenutno stablo ima desne dijece idi desno
                if (stablo->right == n) 
                return stablo;
                else
                 roditelj = ParentB(n, stablo->right);
        }       
        return roditelj; //ako stablo nema ni lijeve ni desne dijece vratit ce 0
}
 
void CreateLeftB(btree *stablo, node n, string x)
{
	if(n->left!=NULL)
	{
		cout <<"Cvor vec ima dijete...\n" << endl;
		return;
	}
	else
	{
		node lijevo = new element;
		lijevo->left = NULL;
		lijevo->right = NULL;
		lijevo->label = x;
		n->left = lijevo;
	}
}
 
void CreateRightB(btree *stablo, node n, string x)
{
 
	if(n->right != NULL){
		cout <<"Cvor vec ima desno dijete...\n" << endl;
		return;
	}
	else
	{
		node desno = new element;
		desno->left = NULL;
		desno->right = NULL;
		desno->label = x;
		n->right = desno;
	}
}
 
 
void brisi(btree *stablo, node n)
{
	if(n->left != NULL)
    brisi(stablo,LeftChildB(stablo,n));
	if(n->right != NULL)
    brisi(stablo,RightChildB(stablo,n));
	delete n;
}
 
 
void DeleteB(btree *stablo, node n)
{
	node pom;
    //nadji roditelja elementa kojeg zelimo brisati i snimamo ga u pom
	pom = ParentB(stablo,n);
	if(LeftChildB(stablo,pom)==n)//ako je to lijevo dijete
	{
		pom->left = NULL;//taj pokazivac stavljamo na 0
	}
	else
	{
		pom->right = NULL;//ako je desno onda taj pokazivac stavljamo na 0
	}
	brisi(stablo,n);//brisemo cvor n i svo njegovo "potomstvo"
}
 
void InitB (string x, node n){
     n->label=x;
     n->right=NULL;
     n->left=NULL;
     }