#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);
		}
	}
}

node* usun_liscie(node*root) {
	if (root != NULL)
	{
		if (root->L == NULL && root->P == NULL)
		{
			delete root;
			return NULL;
		}
		else
		{
			root->L = usun_liscie(root->L);
			root->P = usun_liscie(root->P);
		}
	}
	return root;
}

node* max(node*root) {
	while (root->P) root = root->P;
	return root;
}

void poprzednik(node*root, node*&pop, int x) {
	if (root == NULL) {
		pop = NULL;
		return;
	}
		if (root->val == x) {
			if (root->L) {
				pop = max(root->L);
			}
		}
		else if (x < root->val) {
			poprzednik(root->L, pop, x);
		}
		else {
			pop = root;
			poprzednik(root->P, pop, x);
		}

}

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;
	node*pop = NULL;
	poprzednik(root, pop, 17);
	cout << "Poprzednik dla wartosci wprowadzonej w funkcji wyzej (17) to: " <<pop->val << endl;

	system("PAUSE");
	return 0;
}