// Binary Search Tree ( BST )
// Abdullah Al-Barrak

#include <iostream>
using std::cout;
using std::endl;
using std::cin;

//#include <>

class TreeNode
{
public:
	TreeNode( int );
	~TreeNode();
	
// Data Members:	
	int data;
	TreeNode* left;
	TreeNode* right;
};

TreeNode::TreeNode( int newData )
{
	data = newData;
	left = NULL;
	right = NULL;
}

TreeNode::~TreeNode()
{
	left = NULL;
	right = NULL;
}


class BinarySearchTree
{
public:
	BinarySearchTree();
	~BinarySearchTree();
	
	void destroySubTree( TreeNode* );
	
	void insert( int );
	bool search( int, TreeNode* );
	int findSmallest( TreeNode* );
	int findBiggest( TreeNode* );
	//void deleteAll();
	
	// Call By Refernce 
	void insertWithPointer( int, TreeNode*& );
	void deleteNode( int, TreeNode*& );
	
	
	void makeDeletion01( TreeNode*& );
	void makeDeletion02( TreeNode*& );
	
	// Three Printing methods:
	void print_PLR( TreeNode* ); // Preorder
	void print_LPR( TreeNode* ); // Inorder
	void print_LRP( TreeNode* ); // postorder
	
	// Function that adds all the nodes' values
	int getSum( TreeNode* );
	
	void deleteNodeWithOneChild( TreeNode*& );
	
	int height( TreeNode* );
	int getMax( int, int );
	
	//void mirror( TreeNode*& );
	
	int numberOfleaves( TreeNode* );
	
	int size( TreeNode* );

public: 
	// To use directly:
	void print_PLR() { print_PLR( root ); }	
	void print_LPR() { print_LPR( root ); }	
	void print_LRP() { print_LRP( root ); }
	bool search( int num ) { return search( num, root ); }
	
	// To use directly:
	void insertWithPointer( int num ) { insertWithPointer( num, root ); }
	void deleteNode( int num ) { deleteNode( num, root ); }
	
	// To use directly:
	int findSmallest() { return findSmallest( root ); }
	int findBiggest() { return findBiggest( root ); }
	
	int numberOfleaves() { return numberOfleaves( root ); }
	
	
	
	
// Data Members:
	TreeNode* root;
};

BinarySearchTree::BinarySearchTree()
{
	root = NULL;
}

BinarySearchTree::~BinarySearchTree()
{
	//deleteAll();
	/*
	.
	.
	.
	*/
	destroySubTree( root );
}

void BinarySearchTree::destroySubTree( TreeNode* currentPtr )
{
	if ( currentPtr -> right != NULL )
		destroySubTree( currentPtr -> right );
	
	if ( currentPtr -> left != NULL )
		destroySubTree( currentPtr -> left );
	
	deleteNode( currentPtr -> data );
}

void BinarySearchTree::insert( int nd )
{
	TreeNode* newTreeNode = new TreeNode( nd );
	TreeNode* currentPtr = root;
	
	if ( currentPtr != NULL )
		{
		while ( currentPtr != NULL )
			{
			if ( currentPtr -> data < nd )
				{
				if ( currentPtr -> right != NULL )
					currentPtr = currentPtr -> right;
				else
					{
					currentPtr -> right = newTreeNode;
					break;
					}
				}
			else
				{
				if ( currentPtr -> left != NULL )
					currentPtr = currentPtr -> left;
				else
					{
					currentPtr -> left = newTreeNode;
					break;
					}
				}
			}
		}
	else
		root = newTreeNode;
}

void BinarySearchTree::insertWithPointer( int nd, TreeNode*& currentPtr )
{
	if ( currentPtr == NULL )
		{
		TreeNode* newNode = new TreeNode( nd );
		currentPtr = newNode;
		}
	else 
		if ( nd < currentPtr -> data )
			insertWithPointer( nd, currentPtr -> left );
		else 
			if ( nd > currentPtr -> data )
				insertWithPointer( nd, currentPtr -> right );
			else
				cout <<"Duplicate value found in the tree!\n";
}

bool BinarySearchTree::search( int sd, TreeNode* currentPtr )
{
	if ( currentPtr != NULL )
		{
		if ( currentPtr -> data == sd )
			return true;
		else 
			if ( currentPtr -> data < sd )
				return search( sd, currentPtr -> right );
			else
				return search( sd, currentPtr -> left );
		}
	else
		return false;
}

void BinarySearchTree::deleteNode( int num, TreeNode*& nodePtr )
{
	if ( nodePtr == NULL )
		return;
	else
		if ( num < nodePtr -> data )
			deleteNode( num, nodePtr -> left );
		else
			if ( num > nodePtr -> data )
				deleteNode( num, nodePtr -> right );
			else
				if ( num == nodePtr -> data )
					makeDeletion02( nodePtr ); /*****Choose the makeDeletion function HERE*****/
}


void BinarySearchTree::makeDeletion01( TreeNode*& nodePtr )
{
	TreeNode* tempPtr; //TreeNode* tempPtr = new TreeNode;
	
	if ( nodePtr -> left == NULL )// the node has a right child 
		{
		tempPtr = nodePtr;
		nodePtr = nodePtr -> right;
		delete tempPtr;
		}
	else 
		if ( nodePtr -> right == NULL ) // the node has a left child
			{
			tempPtr = nodePtr;
			nodePtr = nodePtr -> left;
			delete tempPtr;
			}
		else // the node has two childs
			{
			TreeNode* tempPtr = nodePtr -> right;
			//tempPtr = tempPtr -> right;
			
			while ( tempPtr -> left != NULL )
				tempPtr = tempPtr -> left;
				
			tempPtr -> left = nodePtr -> left;
			tempPtr = nodePtr;
			
			nodePtr = nodePtr -> right;
			delete tempPtr;
			}
}

void BinarySearchTree::makeDeletion02( TreeNode*& nodePtr )
{
	TreeNode* tempPtr; //TreeNode* tempPtr = new TreeNode;
	
	if ( nodePtr -> left == NULL )// the node has a right child 
		{
		tempPtr = nodePtr;
		nodePtr = nodePtr -> right;
		delete tempPtr;
		}
	else 
		if ( nodePtr -> right == NULL ) // the node has a left child
			{
			tempPtr = nodePtr;
			nodePtr = nodePtr -> left;
			delete tempPtr;
			}
		else // the node has two childs
			{
			TreeNode* tempPtr = nodePtr -> left;
			//tempPtr = tempPtr -> right;
			
			while ( tempPtr -> right != NULL )
				tempPtr = tempPtr -> right;
				
			tempPtr -> left = nodePtr -> left;
			tempPtr = nodePtr;
			
			nodePtr = nodePtr -> right;
			delete tempPtr;
			}
}

int BinarySearchTree::findBiggest( TreeNode* currentPtr )
{
	
	//Recursive:
	if ( currentPtr != NULL )
		{
		if ( currentPtr -> right != NULL )
			findBiggest( currentPtr -> right );
		else
			return currentPtr -> data;
		}
	//else
		//return -1;
	
	/* //Using While:
	if ( currentPtr != NULL )
		{
		while ( currentPtr -> right != NULL )
			currentPtr = currentPtr -> right;
		
		return currentPtr -> data;
	    }
	else
		return -1;*/
}

int BinarySearchTree::findSmallest( TreeNode* currentPtr )
{
	if ( currentPtr != NULL )
		{
		while ( currentPtr -> left != NULL )
			currentPtr = currentPtr -> left;
		
		return currentPtr -> data;
	    }
	else
		return -1;
}

int BinarySearchTree::getSum( TreeNode* currentPtr )
{
	static int total = 0;
	
	if ( currentPtr != NULL )
		{
		total += currentPtr -> data;
		
		getSum( currentPtr -> right );
		getSum( currentPtr -> left );
		}
		
	return total;
}

void BinarySearchTree::deleteNodeWithOneChild( TreeNode*& currentPtr )
{
	if ( currentPtr != NULL )
		{
		if ( currentPtr -> right == NULL && currentPtr -> left != NULL ) //has a left child
			{
			TreeNode* temp = currentPtr;
			currentPtr = currentPtr -> left;
			delete temp;
			deleteNodeWithOneChild( currentPtr );
			}
		else
			if ( currentPtr -> left == NULL && currentPtr -> right != NULL )  //has a right child
				{
				TreeNode* temp = currentPtr;
				currentPtr = currentPtr -> right;
				delete temp;
				deleteNodeWithOneChild( currentPtr );
				}
			else
				{
				deleteNodeWithOneChild( currentPtr -> right );
				deleteNodeWithOneChild( currentPtr -> left );
				}
		}
}


int BinarySearchTree::height( TreeNode* currentPtr )
{
	if ( currentPtr == NULL )
		return -1;
	else
		{
		if ( currentPtr -> right == NULL && currentPtr -> left == NULL )
			return 0;
		else
			return 1 + getMax( height( currentPtr -> right ), height( currentPtr -> left ) );
		}
}

int BinarySearchTree::getMax( int n1, int n2 )
{
	if ( n1 > n2 )
		return n1;
	else
		return n2;
}

int BinarySearchTree::numberOfleaves( TreeNode* currentPtr )
{
	static int leavesNum = 0;
	
	if ( currentPtr != NULL )
		{
		if ( currentPtr -> right == NULL && currentPtr -> left == NULL )
			leavesNum++;

		numberOfleaves( currentPtr -> right );
		numberOfleaves( currentPtr -> left );
		}
	
	return leavesNum;	
}

/*void BinarySearchTree::mirror( TreeNode*& currentPtr )
{
	if ( currentPtr != NULL )
		{
		TreeNode* temp = currentPtr -> right;
		currentPtr -> right = currentPtr -> left;
		currentPtr -> left = temp;
		mirror( currentPtr -> right );
		mirror( currentPtr -> left );
		}
}*/

int BinarySearchTree::size( TreeNode* currentPtr )
{
	static int Size = 0;
	
	if ( currentPtr != NULL )
		{
		Size++;

		size( currentPtr -> right );
		size( currentPtr -> left );
		}
		
	return Size;
}

void BinarySearchTree::print_PLR( TreeNode* currentPtr )
{
    if ( currentPtr != NULL )
		{
		cout << currentPtr -> data << endl;
		print_PLR( currentPtr -> left );
		print_PLR( currentPtr -> right );
		}
}

void BinarySearchTree::print_LPR( TreeNode* currentPtr )
{
	if ( currentPtr != NULL )
		{
		print_LPR( currentPtr -> left );
		cout << currentPtr -> data << endl;
		print_LPR( currentPtr -> right );
		}
}

void BinarySearchTree::print_LRP( TreeNode* currentPtr )
{
	if ( currentPtr != NULL )
		{
		print_LRP( currentPtr -> left );
		print_LRP( currentPtr -> right );
		cout << currentPtr -> data << endl;
		}
}




int main()
{
	BinarySearchTree tree;
	tree.insert(12);
	tree.insert(10);
	tree.insert(2);
	//tree.insert(16);
	//tree.insert(25);
	//tree.insert(27);
	//tree.insert(30);
	//tree.insert(35);
	//tree.insert(40);
	//tree.insert(10);
	//tree.insertWithPointer( 4 );
	
	cout <<"Smallest element is: " << tree.findSmallest() << endl;
	cout <<"Biggest element is: " << tree.findBiggest() << endl;
	
	
	cout <<"\nPreorder:" << endl;
	tree.print_PLR();	
	
	
    /*******************************
    int sd = 12;
	if ( tree.search( sd ) )
		cout << sd <<" Found!\n";
	else
		cout << sd << " Not found!\n";
  **********************************/
	
	//tree.deleteNode( 10 );
	
	cout <<"\nPostorder:" << endl;
    tree.print_LRP();
	cout <<"\nInorder:" << endl;
	tree.print_LPR();
	
	//tree.mirror( tree.root);
	
	cout <<"The sum is: " << tree.getSum( tree.root ) << endl;
	cout <<"Number of leaves is: " << tree.numberOfleaves( tree.root ) << endl;
	cout <<"Height is: " << tree.height( tree.root ) << endl;
	cout <<"The size is: " << tree.size( tree.root ) << endl;
	
	
	tree.deleteNodeWithOneChild( tree.root );
	tree.print_PLR();
	
	/*****************************
	// Testing destroySubTree:
	tree.destroySubTree( tree.root );
	
	if ( tree.root == NULL )
		cout <<"TRUE, root = NULL \n";
	
	tree.insert(16);
	tree.insert(8);
	
	tree.print_PLR();**************/
	
	system("PAUSE");
	return 0;
}