#include<iostream>
#include<cstdlib> 
using namespace std;

struct element{
	int label;
	element *lijevo,*desno;
};

struct BinaryTree{
	element *korijen;
};

struct stack{
	element * elementi[ 10000 ];
	int top;
};

void InitS( stack& S ){
	S.top = 9999;
}

bool IsEmptyS( stack& S ){
	return S.top == 9999;
}

element * TopS( stack& S ){
	if( !IsEmptyS( S ) )
		return S.elementi[ S.top+1 ];
	else
		return 0;
}

void PushS( element * x, stack& S ){
   if( S.top >= 0 )
      S.elementi[ S.top-- ] = x;
   else
      exit( 1 );
}

void PopS( stack& S ){
   if( !IsEmptyS( S ) )
      S.top++;
   else
      exit( 1 );
}

void InitB( int x, BinaryTree* stablo ){
	stablo->korijen = new element; 
	stablo->korijen->lijevo = stablo->korijen->desno = 0; 
	stablo->korijen->label = x; 
}

element * RootB( BinaryTree* stablo ){
	if( stablo ) 
		return stablo->korijen; 
	return 0; 
}

int LabelB( element * n, BinaryTree* stablo ){
	return n->label; 
}

void ChangeLabelB( int x, element * n, BinaryTree* stablo ){
	n->label = x;
}

element * LeftChildB( element * n, BinaryTree* stablo ){
	if( n->lijevo ) 
		return n->lijevo; 
	return 0; 
}

element * RightChildB( element * n, BinaryTree* stablo ){
	if( n->desno != 0 )
		return n->desno;
	return 0;
}

void CreateLeftB( int x, element * n, BinaryTree* stablo ){
	if( n->lijevo != 0) 
		cout << "Error!" << endl; 
	else{
		element * novi = new element;  
		novi->label = x;          
		novi->lijevo = novi->desno = 0; 
		n->lijevo = novi; 
	}
}

void CreateRightB( int x, element * n, BinaryTree* stablo ){
	if( n->desno != 0)
		cout << "Error!" << endl;
	else{
		element * novi = new element;
		novi->label = x;
		novi->lijevo = novi->desno = 0;
		n->desno = novi;
	}
}

element * ParentB( element * n, BinaryTree* stablo ){
	element * tekuci; 
	bool nadjen=false; 
	stack S; 
	InitS(S); 
	PushS( stablo->korijen,S); 
	while((!IsEmptyS(S)) && (!nadjen)) { 
		tekuci=TopS(S);	
		PopS( S );			
		if ((tekuci->lijevo!=n) && (tekuci->desno!=n)){ 
			if (tekuci->lijevo!=0) PushS(tekuci->lijevo,S);
			if (tekuci->desno!=0) PushS(tekuci->desno,S); 
		}
		else
			nadjen = true; 
	}
	if( nadjen ) 
		return tekuci;
	else 
		return 0;
}

void DeleteElement( element * n, BinaryTree* stablo ){
	if( n->lijevo ) DeleteElement( n->lijevo, stablo ); 
	if( n->desno ) DeleteElement( n->desno, stablo ); 
	delete n; 
}

void DeleteB( element * n, BinaryTree* stablo ){
	element * l = n; 
	if( n->lijevo ) DeleteElement( n->lijevo, stablo ); 
	if( n->desno ) DeleteElement( n->desno, stablo ); 
	l = ParentB( n, stablo ); 
	if( l != 0 ){ 
		if( l->lijevo == n ) 
			l->lijevo = 0; 
		else
			l->desno = 0; 
	delete n; 
	}
	else{
		delete stablo->korijen; 
		stablo->korijen = 0; 
	}
}

bool ExistsLeftChildB( element * n, BinaryTree* stablo ){
	if( LeftChildB( n, stablo ) != 0 )
		return true;
	else
		return false;
}

bool ExistsRightChildB( element * n, BinaryTree* stablo ){
	if( RightChildB( n, stablo ) != 0 )
		return true;
	else
		return false;
}