#include <iostream>

using namespace std;

struct node {
	int val;
	node *P;
	node *L;
	node *O;
};

void insertBST(node *& root, int val) {
	if (root == NULL) {
		root = new node;
		root->val = val;
		root->L = root->P = NULL;
	}
	else {
		if (val < root->val) {
			insertBST(root->L, val);
			root->L->O = root;
		}
		else {
			insertBST(root->P, val);
			root->P->O = root;
		}
	}
}

void inorder(node *root) {
	if (root != NULL) {
		inorder(root->L);
		cout << root->val << " ";
		inorder(root->P);
	}
}

void find_sek(node*root, int val) {
	while (root) {
		if (root->val == val) {
			cout << "element istnieje!" << endl;
			break;
		}
		else if (root->val > val) {
			root = root->L;
		}
		else {
			root = root->P;
		}
	}
}

void find_rek(node*root, int val) {
	if (root != NULL) {
		if (root->val == val) {
			cout << "element istnieje" << endl;
		}
		else if (root->val > val) {
			find_rek(root->L, val);
		}
		else {
			find_rek(root->P, val);
		}
	}
}

struct node* usun_liscie(struct node*root) {
	if (root != NULL)
	{
		if (root->L == NULL && root->P == NULL)
		{
			node * p = new node;
			p = root->P;
			root->P = NULL;
			delete p;

			return NULL;
		}
		else
		{
			root->L = usun_liscie(root->L);
			root->P = usun_liscie(root->P);
		}
	}


	return root;
}

int main()
{
	node*root = NULL;
	insertBST(root, 15);
	insertBST(root, 6);
	insertBST(root, 18);
	insertBST(root, 17);
	insertBST(root, 20);
	insertBST(root, 3);
	insertBST(root, 7);
	insertBST(root, 2);
	insertBST(root, 4);
	insertBST(root, 13);
	insertBST(root, 9);

	inorder(root);
	cout << endl;
	usun_liscie(root);
	inorder(root);
	cout << endl;

	system("PAUSE");
	return 0;
}