#include <iostream.h>


struct TreeNode
{
	int key;
	TreeNode *left;
	TreeNode *right;
};


class BinarySearchTree
{
public:
	TreeNode *root;



	BinarySearchTree(){root=0;}
	
	void insert( int z, TreeNode* &root )
	{
		if(root==0)
		{
			root = new TreeNode;
			root->left = 0;
			root->right = 0;
			root->key = z;
			return;
		}

		if(z<root->key)
		{
			insert(z, root->left);
		}
		else
		{
			insert(z, root->right);
		}
	}

	TreeNode* search(int z, TreeNode* root)			// kein &root nötig, da wurzel nicht manipuliert wird!
	{
		if( root==0 || z==root->key )
		{
			return root;
		}

		if( z<root->key )
		{
			return search(z, root->left);
		}
		else
		{
			return search(z, root->right);
		}
	}


	void remove(int z, TreeNode* &root)
	{
		if(root==0) return;

		if(z==root->key)
		{
			if(root->left==0 || root->right==0)
			{
				TreeNode* p=root;
				if(root->left==0)
				{
					root=root->right;
				}
				else
				{
					root=root->left;
				}
				delete p;
				return;
			}
			root->key=deleteMin(root->right);
			return;
		}

		if(z<root->key)
		{
			remove(z, root->left);
		}
		else
		{
			remove(z, root->right);
		}
	}

	int deleteMin( TreeNode* &root)
	{
		if(root->left==0)
		{
			TreeNode* p=root;
			int h=root->key;
			root=root->right;
			delete p; 
			return h;
		}
		return deleteMin(root->left);
	}


	void inorder( TreeNode* root)
	{
		if(root!=0)
		{
			inorder(root->left);
			cout << root->key << endl;
			inorder(root->right);
		}
	}

	void preorder( TreeNode* root)
	{
		if(root!=0)
		{
			cout << root->key << endl;
			preorder(root->left);
			preorder(root->right);
		}
	}

	void postorder( TreeNode* root)
	{
		if(root!=0)
		{
			postorder(root->left);
			postorder(root->right);
			cout << root->key << endl;
		}
	}

};




int main()
{
	BinarySearchTree myTree;
	myTree.insert(5,myTree.root);
	myTree.insert(1,myTree.root);
	myTree.insert(7,myTree.root);
	myTree.insert(22,myTree.root);

	TreeNode* res = myTree.search(7,myTree.root);
	cout << res->key << endl << endl;

	myTree.postorder(myTree.root);
	cout << endl;

	myTree.remove(7, myTree.root);
	myTree.preorder(myTree.root);

	return 0;
}