// BST_Delete.cpp : Defines the entry point for the console application.
//tree.cpp
//demonstrates binary tree
#include <iostream>
#include <stack>
using namespace std;
/////////////////////////////////////////////////////////////
class Node
   {
   public:
      int iData;                //data item (key)
      double dData;             //data item
      Node* pLeftChild;         //this node's left child
      Node* pRightChild;        //this node's right child
//----------------------------------------------------------
                                //constructor
      Node() : iData(0), dData(0.0), pLeftChild(NULL),
                                     pRightChild(NULL)
         {  }
//----------------------------------------------------------
      ~Node()                   //destructor
         { cout << "X-" << iData << " "; }
//----------------------------------------------------------
      void displayNode()        //display ourself: {75, 7.5}
         {
         cout << '{' << iData << ", " << dData << "} ";
         }
   };  //end class Node
/////////////////////////////////////////////////////////////
class Tree
   {
   private:
      Node* pRoot;              //first node of tree

   public:
//----------------------------------------------------------
   Tree() : pRoot(NULL)         //constructor
      {  }
//----------------------------------------------------------
   Node* find(int key)          //find node with given key
      {                         //(assumes non-empty tree)
      Node* pKeyPointer = pRoot;             //start at root
      while(pKeyPointer->iData != key)       //while no match,
         {
         if(key < pKeyPointer->iData)        //go left?
            pKeyPointer = pKeyPointer->pLeftChild;
         else                             //or go right?
            pKeyPointer = pKeyPointer->pRightChild;
         if(pKeyPointer == NULL)             //if no child,
            return NULL;                  //didn't find it
         }
      return pKeyPointer;                    //found it
      }  //end find()
//-----------------------------------------------------------
   void del (int key)
   {
	   Node* KeyPointer;
	   Node* current;
	   Node* parent;
	   Node* temp;

	   KeyPointer = pRoot;
	   while (KeyPointer->iData != key) //finding the pointer with key data
	   {
		   if (KeyPointer->iData > key)
		   {
			   KeyPointer = KeyPointer->pLeftChild;
		   }
		   else if (KeyPointer->iData < key)
		   {
			   KeyPointer = KeyPointer->pRightChild;
		   }
	   } //when loop ends, KeyPointer will be pointer with key

	   if (KeyPointer = NULL)
	   {
		   cout << "Node to be deleted is NULL" << endl;
	   }

	   else if (KeyPointer->pRightChild == NULL && KeyPointer->pLeftChild == NULL) //case 1: No child
	   {
		   temp = KeyPointer;
		   KeyPointer = NULL;
		   delete temp;
	   }

	   else if (KeyPointer->pRightChild == NULL) //case 2: one child
	   {
		   temp = KeyPointer;
		   KeyPointer = KeyPointer->pLeftChild;
		   delete temp;
	   }

	   else if (KeyPointer->pLeftChild == NULL)
	   {
		   temp = KeyPointer;
		   KeyPointer = KeyPointer->pRightChild;
		   delete temp;
	   }

	   else //case 3: two child
	   {
		   current = KeyPointer->pRightChild; //smallest of right subtree approach
		   parent = NULL;

		   while (current->pLeftChild != NULL)
		   {
			   parent = current;
			   current = current->pLeftChild;
		   }

		   KeyPointer->iData = current->iData; //swapping data

		   if (parent == NULL) //did not traverse,
		   {
			   KeyPointer->pRightChild = current->pRightChild;
		   }

		   else //to link any subtrees under deleted node
		   {
			   parent->pLeftChild = current->pRightChild;
		   }

		   delete current;
	   }
   }//end delete
//-----------------------------------------------------------
   void insert(int id, double dd) //insert new node
      {
      Node* pNewNode = new Node;         //make new node
      pNewNode->iData = id;              //insert data
      pNewNode->dData = dd;
      if(pRoot==NULL)                    //no node in root
         pRoot = pNewNode;
      else                               //root occupied
         {
         Node* pKeyPointer = pRoot;         //start at root
         Node* pParent;
         while(true)                     //(exits internally)
            {
            pParent = pKeyPointer;
            if(id < pKeyPointer->iData)     //go left?
               {
               pKeyPointer = pKeyPointer->pLeftChild;
               if(pKeyPointer == NULL)     //if end of the line,
                  {                     //insert on left
                  pParent->pLeftChild = pNewNode;
                  return;
                  }
               }  //end if go left
		//if num to be inserted matches existing numbers
		//insert on right
            else                          //or go right?
               {
               pKeyPointer = pKeyPointer->pRightChild;
               if(pKeyPointer == NULL)     //if end of the line
                  {                     //insert on right
                  pParent->pRightChild = pNewNode;
                  return;
                  }
               }  //end else go right
            }  //end while
         }  //end else not root
      }  //end insert()
//-----------------------------------------------------------
   void traverse(int traverseType)
      {
 		//your code
		switch (traverseType)
		{
			case 1: cout << "\nPreorder traversal: ";
					preOrder (pRoot);
					break;

			case 2: cout << "\nInorder traversal: ";
					inOrder (pRoot);
					break;

			case 3: cout << "\nPostorder traversal: ";
					postOrder (pRoot);
					break;
		}
		cout << endl;
      }
//-----------------------------------------------------------
   void preOrder(Node* pLocalRoot)
      {
 		//your code
		if (pLocalRoot != NULL)
		{
			cout << pLocalRoot -> iData << " " ;
			preOrder (pLocalRoot -> pLeftChild);
			preOrder (pLocalRoot -> pRightChild);
		}

      }
//----------------------------------------------------------
   void inOrder(Node* pLocalRoot)
      {
		//your code
		if (pLocalRoot != NULL)
		{
		  inOrder (pLocalRoot -> pLeftChild);
		  cout << pLocalRoot -> iData << " " ;
		  inOrder (pLocalRoot -> pRightChild);
		  //when it goes to the right, it doesnt print yet
		  //but goes to the left of the one on the right

		  //leftmost: 12
		  //then prints itself: 25
		  //then goes to right (37) to the leftmost: 30
		  //then prints itself (30)
		  //then goes to the right: 33
		  //done with leftChild of 37
		  //prints itself: 37
		}
      }
//---------------------------------------------------------
   void postOrder(Node* pLocalRoot)
      {
		//your code
		if (pLocalRoot != NULL)
		{
			postOrder (pLocalRoot -> pLeftChild);
			postOrder (pLocalRoot -> pRightChild);
			cout << pLocalRoot -> iData << " " ;
		}
      }
//-----------------------------------------------------------
   void displayTree()
      {
      stack<Node*> globalStack;
      globalStack.push(pRoot);
      int nBlanks = 32;
      bool isRowEmpty = false;

      cout <<
      "....................................................";
      cout << endl;
      while(isRowEmpty==false)
         {
         stack<Node*> localStack;
         isRowEmpty = true;

         for(int j=0; j<nBlanks; j++)
            cout << ' ';

         while(globalStack.empty()==false)
            {
            Node* temp = globalStack.top();
            globalStack.pop();
            if(temp != NULL)
               {
               cout << temp->iData;
               localStack.push(temp->pLeftChild);
               localStack.push(temp->pRightChild);

               if(temp->pLeftChild != NULL ||
                                temp->pRightChild != NULL)
                  isRowEmpty = false;
               }
            else
               {
               cout << "--";
               localStack.push(NULL);
               localStack.push(NULL);
               }
            for(int j=0; j<nBlanks*2-2; j++)
               cout << ' ';
            }  //end while globalStack not empty
         cout << endl;
         nBlanks /= 2;
         while(localStack.empty()==false)
            {
            globalStack.push( localStack.top() );
            localStack.pop();
            }
         }  //end while isRowEmpty is false
      cout <<
      "...................................................";
      cout << endl;
      }  //end displayTree()
//---------------------------------------------------------
   void destroy()                        //deletes all nodes
      { destroyRec(pRoot); }             //start at root
//---------------------------------------------------------
   void destroyRec(Node* pLocalRoot)     //delete nodes in
      {                                  // this subtree
      if(pLocalRoot != NULL)
       {                                 //uses postOrder
        destroyRec(pLocalRoot->pLeftChild);  //left subtree
        destroyRec(pLocalRoot->pRightChild); //right subtree
        delete pLocalRoot;               //delete this node
       }
      }
//----------------------------------------------------------
   };  //end class Tree
////////////////////////////////////////////////////////////
int main()
   {
   int value;
   char choice;
   Node* found;
   Tree theTree;                          //create tree

   theTree.insert(50, 5.0);               //insert nodes
   theTree.insert(25, 2.5);
   theTree.insert(75, 7.5);
   theTree.insert(12, 1.2);
   theTree.insert(37, 3.7);
   theTree.insert(43, 4.3);
   theTree.insert(30, 3.0);
   theTree.insert(33, 3.3);
   theTree.insert(87, 8.7);
   theTree.insert(93, 9.3);
   theTree.insert(97, 9.7);


	  do                   //interact with user
      {                     //until user types 'q'
      cout << "\nEnter first letter of ";
    cout << "show, insert, find, traverse, delete or quit: ";
      cin >> choice;
      switch(choice)
         {
         case 's':                        //show the tree
            theTree.displayTree();
            break;
         case 'i':                        //insert a node
            cout << "Enter value to insert: ";
            cin >> value;
            theTree.insert(value, value * 0.1);
		 cout << value << " has been inserted" << endl;
            break;
         case 'f':                        //find a node
            cout << "Enter value to find: ";
            cin >> value;
            found = theTree.find(value);
            if(found != NULL)
               {
               cout << "Found: ";
               found->displayNode();
               cout << endl;
               }
            else
               cout << "Could not find " << value << endl;
            break;
         case 't':                     //traverse the tree
            cout << "Enter traverse type (1=preorder, "
                 << "2=inorder, 3=postorder): ";
            cin >> value;
            theTree.traverse(value);
            break;
         case 'q':                    //quit the program
            theTree.destroy();
            cout << endl;
            break;

		 case 'd':
			 cout << "Enter value to delete: ";
			 cin >> value;
            found = theTree.find(value);

			if (found != NULL)
			{
			  theTree.del(value);
		 cout << value << " has been deleted" << endl;
			}

            else
               cout << "Could not find " << value << endl;

			 cout << endl;
			 break;

         default:
            cout << "Invalid entry\n";
         }  //end switch
      } while(choice != 'q');  //end while

   system("pause");
   return 0;
   }  //end main()