// implementation of BST
// does not allow duplicate items
// wdg 2008

#include <iostream>
#include "BinarySearchTree.h"
using namespace std;

// constructor creates an empty tree

    BinarySearchTree::BinarySearchTree( ) : root(NULL) , count(0)  
    {
    }
//======================================================================
// GENERAL BINARY SEARCH TREE METHODS
//======================================================================
// method search starts at root looking for that item
// returns either node where found, or failing that, 
// position where should be attached
// asssumes root!=null

   BSTNode *BinarySearchTree::search( ItemType it ) const
   {	
      BSTNode *v=root;
      bool absent=false;
      while( !absent && it!=v->element ) {
         if( it<v->element && v->left!=NULL )
             v = v->left;
         else if( it>v->element && v->right!=NULL )
     	     v = v->right;
         else 
             absent = true;
      }
      return v;
   }
//----------------------------------------------------------------------
// inserts item

   void BinarySearchTree::insertItem(ItemType it)
   {
      insertItem( new BSTNode(it,NULL) );
   }

   bool BinarySearchTree::insertItem(BSTNode *newNode)
   {
     ItemType it = newNode->element;     
     if(count==0) {
          count=1;
 	  root=newNode;
     }
     else {
         BSTNode *v = search(it);
         if( it < v->element ) {
              count++;
              v->left=newNode;                
              newNode->parent = v;
         }
         else if( it > v->element ) {
              count++;
              v->right = newNode;
              newNode->parent = v;
         }
         else {
            cout << it << " duplicate" << endl;
            return false;
         } 
     }
     return true;
  }  
//----------------------------------------------------------------------
// find item

   bool BinarySearchTree::findItem(ItemType it) const
   {
       if(count==0)
           return false;
       ItemType item = search(it)->element;
       if( item == it )
           return true;
        else 
           return false;
    } 
//----------------------------------------------------------------------
// delete item

   bool BinarySearchTree::deleteItem(ItemType it) 
   {      
      BSTNode *toBeDeleted=NULL;
      if( root==NULL)
         return false;
      else if( it == root->element && ( root->left==NULL || root->right== NULL ) ) {
         // root deleted
         toBeDeleted = root;
         if( root->left!=NULL )
             root = root->left;
         else
             root = root->right;
         count--;
         delete toBeDeleted;
         return true;
      } 
      else {      // root not deleted
         BSTNode *parent = NULL;
         BSTNode *curr = root;
         while ( curr!=NULL && curr->element!=it) {
            parent = curr;
            if( it < curr->element ) 
                curr = curr->left;
            else 
                curr = curr->right;
         }
         if( curr==NULL )
            return false;
         else {
            if( curr->left!=NULL && curr->right!=NULL ) {
               BSTNode *hold = curr;
               parent = curr;
               curr = curr->right;
               while ( curr->left!=NULL ) {
                  parent = curr;
                  curr = curr->left;
               }
               hold->element = curr->element;
            }
            toBeDeleted = curr;
            if( curr->left!=NULL ) 
               curr = curr->left;
            else
               curr = curr->right;
            if( toBeDeleted == parent->left )          
               parent->left = curr;
            else
               parent->right = curr;
            count--;
            delete toBeDeleted;
            return true;
          }
       } // end-if root not deleted
  }                
              
//======================================================================
//  OUTPUT METHODS
//======================================================================
   void BinarySearchTree::dumpItemsInOrder( ) const
   {
     if( count==0 )
         cout << "Empty" << endl;
     else {
         inOrder(root);   	
         cout << endl; 
     }
  }
  void BinarySearchTree::inOrder(BSTNode *v) const
  {
    if( v==NULL )
       return;
    inOrder(v->left);
    cout << v->element;
    inOrder(v->right);
 }