#include <iostream>
using namespace std;

struct wezel
{
	wezel *up;
	wezel *left;
	wezel *right;
	int dane;
};
wezel *root = NULL;

void add(int temp)
{
wezel *nowy;
nowy = new wezel;
nowy->dane=temp;
nowy->up=NULL;
nowy->left=NULL;
nowy->right=NULL;
if(root==NULL){
	root=nowy;
}

else{
	wezel *x=root;
	wezel *p=x;	
	
	while(x!=NULL){
		p=x;
		if(nowy->dane<x->dane)
		x=x->left;
		else
		x=x->right;
	}
	if(nowy->dane<p->dane)
	p->left=nowy;
	else
	p->right=nowy;	
	
	nowy->up=p;
}
}
void order(wezel* p){
if(p!=NULL)
{
	order(p->left);
	cout<<p->dane<<" ";
	order(p->right);
}
}


wezel *szukaj(int s, wezel *xs){
if(xs==NULL || xs->dane==s)
	return xs;
else
if(s<xs->dane)
	return szukaj(s,xs->left);
else
	return szukaj(s,xs->right);	
}

wezel *usun(int u,wezel *xu)
{
wezel *temp=szukaj(u,root);

if(temp->left==NULL && temp->right==NULL){
	if(temp->up->right==temp)
		temp->up->right=NULL;
	else
		temp->up->left=NULL;
	delete temp;
}

}


int main(int argc, char* argv){
add(5);
add(3);
add(8);
add(1);
add(4);
add(6);
add(10);
add(7);
add(12);
order(root);
cout<<"\n\n";
cout<<szukaj(12,root);
cout<<"\n\n";
usun(12,root);
order(root);
return 0;

}