#include <iostream>
 
using namespace std;
 
struct bt {
	int label;
	bt *left,*right;
};
 
typedef  bt *node;
typedef bt* btree;
 
void InitB(int x, btree T){
	T->left=NULL;
	T->right=NULL;
	T->label=x;
}
 
node RootB(btree T){
	return T;
} 
 
int LabelB(node n,btree T){
	return n->label;
}
void ChangeLabelB(int x,node n, btree T){
	n->label=x;
}
 
node ParentB(node n,btree T){
	node parentL=NULL,parentR=NULL;
	if(T->left==n || T->right ==n) return T;
	if(T->left) parentL=ParentB(n,T->left);
	if(T->right) parentR=ParentB(n,T->right);
	if (parentL) return parentL;
	if (parentR) return parentR;
	return NULL;
}
 
node LeftChildB(node n, btree T){
	return n->left;
}
 
node RightChildB(node n, btree T){
	return n->right;
}
 
void CreateLeftB(int x, node n, btree T){
	if (n->left) cout <<"Vec postoji lijevo dijete!"<<endl;
	else{
		node novi=new bt;
		n->left=novi;
		novi->left=NULL;
		novi->right=NULL;
		novi->label=x;		
	}
}
 
void CreateRightB(int x, node n, btree T){
	if (n->right) cout <<"Vec postoji desno dijete!"<<endl;
	else{
		node novi=new bt;
		novi->left=NULL;
		novi->right=NULL;
		novi->label=x;
		n->right=novi;
	}
}
 
void DeleteB(node n, btree T){
	if(n->left) DeleteB(n->left,T);
	if(n->right) DeleteB(n->right,T);
	if(n!=RootB(T) && LeftChildB(ParentB(n,T),T)==n)
			ParentB(n,T)->left=NULL;
		else if (n!=RootB(T))
			ParentB(n,T)->right=NULL;
			cout<<"Izbrisan cvor "<<n->label<<endl;
	delete n;
}
 
bool ExistRightChild(node n,btree T){
	if(n->right==NULL) return false;
	return true;
}
 
bool ExistLeftChild(node n,btree T){
	if(n->left==NULL) return false;
	return true;
}