#include <iostream>

using namespace std;

struct Tree_node
{
	int val;
	Tree_node* left_child;
	Tree_node* right_child;
	Tree_node(int val)
	{
		this->val = val;
		left_child = right_child = nullptr;
	}
	Tree_node(){}
};


class Binary_tree
{
private:
	Tree_node* root;
	int Size;
	int height(Tree_node* currRoot)
	{
		if (currRoot == nullptr)
			return 0;
		int lh = height(currRoot->left_child);
		int rh = height(currRoot->right_child);
		return 1 + (lh > rh ? lh : rh);
	}

	void print(Tree_node* currRoot,int a)
	{
		if (currRoot == nullptr)
		{
			for (int i = 0; i < a + 1; i++) cout << " ";

			cout << "@" << endl;

			return;
		}
		print(currRoot->right_child, a + 4);

		for (int i = 0; i < a; i++)
			cout << " ";
		cout << (currRoot->val) << endl;

		print(currRoot->left_child, a + 4);

	}

	void print_preorder(Tree_node* currRoot)
	{
		if (currRoot == 0)
			return;
		cout << currRoot->val << ' ';
		print_preorder(currRoot->left_child);
		print_preorder(currRoot->right_child);
	}

	void print_inorder(Tree_node* currRoot)
	{
		if (currRoot == 0)
			return;
		print_inorder(currRoot->left_child);
		cout << currRoot->val << ' ';
		print_inorder(currRoot->right_child);
	}

	void print_postorder(Tree_node* currRoot)
	{
		if (currRoot == 0)
			return;
		print_postorder(currRoot->right_child);
		print_postorder(currRoot->left_child);
		cout << currRoot->val << ' ';
	}

	void remove(Tree_node*& currRoot, int val)
	{
		if (currRoot == nullptr)
			return;
		if (currRoot->val != val)
		{
			if (currRoot->val > val)
				remove(currRoot->left_child, val);
			else
				remove(currRoot->right_child, val);
		}
		else
		{
			Tree_node* help = currRoot;
			if (currRoot->left_child == nullptr)
			{
				currRoot = currRoot->right_child;
				delete help;
			}
			else
			{
				if (currRoot->right_child == nullptr)
				{
					currRoot = currRoot->left_child;
					delete help;
				}
				else
				{
					Tree_node* right = currRoot->right_child;
					if (right->left_child == nullptr)
					{
						right->left_child = currRoot->left_child;
						currRoot = right;
						delete help;
					}
					else
					{
						Tree_node* prev = right, *act = prev->left_child;
						while (act->left_child != nullptr)
						{
							prev = prev->left_child;
							act = act->left_child;
						}
						currRoot->val = act->val;
						prev->left_child = act->right_child;
						delete act;
					}
				}
			}
		}
	}
public:
	Binary_tree()
	{
		root = nullptr;
		Size = 0;
	}

	Binary_tree(int val)
	{
		root->val = val;
		root->left_child = root->right_child = nullptr;
		Size = 1;
	}

	~Binary_tree()
	{
		destroy(root);
	}

	void destroy(Tree_node* currRoot)
	{
		if (currRoot == nullptr)
			return;
		destroy(currRoot->left_child);
		destroy(currRoot->right_child);
		delete currRoot;
	}

	bool add(int val)
	{
		if (root == nullptr)
		{
			root = new Tree_node(val);
			Size++;
			return true;
		}
		Tree_node* curr = root;
		while (true)
		{
			if (curr->val == val)
				return false;
			else
				if (curr->val > val)
				{
					if (curr->left_child == nullptr)
					{
						curr->left_child = new Tree_node(val);
						Size++;
						return true;
					}
					else
						curr = curr->left_child;
				}
				else
					if (curr->right_child == nullptr)
					{
						curr->right_child = new Tree_node(val);
						Size++;
						return true;
					}
					else
						curr = curr->right_child;

		}
	}

	int size()
	{
		return Size;
	}

	int height()
	{
		return height(root);
	}

	void print()
	{
		print(root, 0);
		cout << endl;
	}

	void print_preorder()
	{
		print_preorder(root);
		cout << endl;
	}

	void print_inorder()
	{
		print_inorder(root);
		cout << endl;
	}

	void print_postorder()
	{
		print_postorder(root);
		cout << endl;
	}

	void remove(int val)
	{
		remove(root, val);
	}
};


int main()
{
	int a[] = {5,4,9,1,3,2,12,7,6,8};
	Binary_tree tree;
	for (int i = 0; i < 9; i++)
		tree.add(a[i]);
	tree.print_inorder();
	tree.height();
	tree.add(15);
	tree.print_inorder();
	tree.remove(15);
	tree.remove(5);
	tree.add(18);
	tree.print_inorder();


}