#include "stdafx.h"
#include <string>
#include <iostream>
using namespace std;
 
struct item {
   int key;
   item * left;
   item * right;
};
 
item * root;
 
void init () 
{
   root = nullptr;
}
 
void insert (item * & target, int k ) 
{
   if (target == nullptr)
   {
      target = new item;
      target->key = k;
      target->left = nullptr;
      target->right = nullptr;
   }
   else if (target->key == k)
      cout << k <<" uz je ve stromu" << endl;
   else if (k < target->key)
	  insert (target->left, k);
   else 
	  insert (target->right, k);
}
 
item * unlink(item * & target)
{
	if(target->right != nullptr)
	{
		return unlink (target->right);
	}
	else
	{
		item * p = target;
		target = target->left;
		return p;
	}
}
 
void remove (item * & target, int k ) 
{
   if (target == nullptr)
      cout<<"Neni ve stromu"<<endl;
   else if (k < target->key)
	  remove (target->left, k);
   else if (target->key < k)
	  remove (target->right, k);
   else /* if (target->key == k) */
   {
       item * uk = target;
	   if (target->left!=nullptr && target->right==nullptr)
		   target = target->left;
	   else if (target->left==nullptr && target->right!=nullptr)
		   target = target->right;
	   else if (target->left==nullptr && target->right==nullptr)
		   target = nullptr;
	   else /* if (target->left!=nullptr && target->right!=nullptr) */
	   {
                   /*
		   item * p = unlink (target->left);
		   p->left = target->left;
		   p->right = target->right;
		   target = p;
                   */
 
    	           item * u = nullptr;
		   item * p = target->left;
		   if (p->right == nullptr)
		   {
			   target->left = p->left;
			   u = p;
		   }
		   else
		   {
			   while (p->right->right != nullptr)
				   p = p->right;
			   u = p->right;
			   p->right = u->left;
		   }
 
		   u->left = target->left;
		   u->right = target->right;
		   target = u;
 
 
	   }
	   delete uk;
   }
}
 
void add (int k)
{
	insert (root, k);
}
 
void print (item *branch)
{
	if(branch != nullptr)
	{
		print(branch->left);
		cout << branch->key << endl;
		print(branch->right);
	}
}
 
void print (item *branch, int k)
{
	if(branch != nullptr)
	{
		print(branch->left, k+1);
		for (int i = 0; i < k-1; i++) cout << "      ";
		cout << branch->key << endl << endl;
		print(branch->right, k+1);
	}
}
 
void display (item *branch, int k, int max)
{
	if (branch != nullptr)
	{
		if (k < max) display (branch->left, k+1, max);
		if (k == max) cout << branch->key << endl;
		if (k < max) display (branch->right, k+1, max);
	}
}
 
void find(item* branch, int k){
	if(branch == nullptr){
		cout << k << " neni ve stromu" << endl;
	}else if(branch->key == k){
		cout << k << " je ve stromu" << endl;
	}else if(branch->key < k){
		find(branch->right, k);
	}else{
		find(branch->left, k);
	}
}
 
bool lookup (item* branch, int k){
	if(branch == nullptr)
		return false;
	else if(branch->key == k)
		return true;
	else if(branch->key < k)
		return lookup(branch->right, k);
	else
		return lookup(branch->left, k);
}
 
bool search (int k)
{
    item * branch = root;
	while (branch != nullptr)
	{
	  if (branch->key == k)
		 return true;
	  else if (branch->key < k)
		branch = branch->right;
	 else
		branch = branch->left;
	}
    return false;
}
 
int _tmain(int argc, _TCHAR* argv[])
{
	init ();
	add (10); add (5); add (1); add (7); add (2); add (4); add (3);
	remove (root, 5);
 
	// find(root, 2);
	// find(root, 5);
	// cout << "1. patro" << endl;
	// display (root, 1, 1);
	// cout << "2. patro" << endl;
	// display (root, 1, 2);
	// print(root);
	print(root, 1);
 
	cout << "Konec - stisknete enter" << endl;
 
	char c;
	cin >> c;
 
    return 0;
}