#include "BST.h"
#include <iomanip.h>
#include"Stack.cpp"


BinarySearchTree::BinarySearchTree()
{
  root = NULL;
  tsize=0;
}
/******************************************************************************/ 
BinarySearchTree::~BinarySearchTree( )
{}
/******************************************************************************/ 
/*bool BinarySearchTree::isEmpty()
{
  if(root=NULL)
     return false;
  else return true;
}*/

BinaryNode* BinarySearchTree::getroot()
{
  return root;
}
/******************************************************************************/ 
void BinarySearchTree::insert( BinaryNode& node )
{
  insert(root,node); 
}
/******************************************************************************/ 
void BinarySearchTree::insert(  BinaryNode* & rnode , const BinaryNode& node )
{
  if( rnode == NULL )
      rnode = new BinaryNode( node );
  else if( node.number < rnode->number )
         { insert( rnode->left , node );
           tsize++;}
       else if( node.number > rnode->number )
              { insert( rnode->right , node );
                tsize++;}
            else
                cout<<"\n           Record with same name already exist... \n";  // Duplicate; do nothing         
}
/******************************************************************************/ 
int BinarySearchTree::getsize()
{
 return tsize;
}

/******************************************************************************/
void BinarySearchTree::remove( int x )
{
  remove(root,x); 
}
/******************************************************************************/ 
void BinarySearchTree::remove(BinaryNode* &t, int x )
{
        
  if( t == NULL )
     return;   // Item not found; do nothing
  if( x < t->number )
      remove(  t->left , x );
  else if( t->number < x )
           remove(  t->right, x );
       else if( t->left != NULL && t->right != NULL ) // Two children
       {   
                BinaryNode *temp = t->right;
                while( temp->left != NULL ) 
                temp = temp->left;
                t->number = temp->number;
                remove(  t->right ,t->number );
       }
            else
            {
                BinaryNode *nodeToDelete = t;
                t = ( t->left != NULL ) ? t->left : t->right;
                delete nodeToDelete;
            }
}
/******************************************************************************/ 
const BinaryNode* BinarySearchTree:: find( int num ) const
{
          if( root == NULL ){
              cout<<"\n              ....   Tree is Empty  ...\n";
              return NULL;
          }    
         cout<< endl<<num<< endl;
          BinaryNode *temp = root;  
          
          while( temp != NULL && temp->number != num ) {
              if( temp->number > num )
                temp=temp->left ;
              else  
                temp=temp->right ;
           }     
         
          
            if ( temp != NULL ) {

                   cout<< "\n Number"<<temp->number<<" is exists in tree "<<endl<<endl;
              return temp;
           }   
           
           cout<< "\n Number "<<num<<" NOT FOUND "<<endl<<endl;

                    return NULL;
}
/******************************************************************************/ 
void BinarySearchTree::height() 
{
           cout<<endl<<"                      Height of the BST is " <<height(root)<<endl;   
}
/******************************************************************************/ 
int BinarySearchTree::height(BinaryNode *rootNode) {
     
      int leftHeight, rightHeight; 

      if (rootNode == NULL) { 
         return -1; 
      } 
      leftHeight = height(rootNode->left); 
      rightHeight = height(rootNode->right); 
      if (leftHeight > rightHeight) { 
          return leftHeight+1; 
      } else { 
          return rightHeight+1; 
    } 
}
/******************************************************************************/ 
void BinarySearchTree::print( )const 
{
  printInorder(root);
}
/******************************************************************************/        
void BinarySearchTree::printInorder( BinaryNode *temp ) const
{
  if (temp != NULL)
  {
      printInorder(temp->left);
      cout<< endl<< "    Number = "<<setw(20)<< temp->number; 
      printInorder(temp->right);
  }  
                  
}
/******************************************************************************/

int BinarySearchTree::sum()
{
   sum(root);
}

/******************************************************************************/
int BinarySearchTree::sum(BinaryNode * rootNode)
{
    int sum=0;
    Stack<BinaryNode* > stack; 
    BinaryNode* p;
    p = root;
    do
    {
        while( p != NULL )
        {
            stack.push( p );
            p = p->left;
        }
        // at this point, left tree is empty 
	 if( !stack.isEmpty() )
	 {
        	p = stack.pop();
        	sum=sum+p->number;
           	p = p->right; 
	 }
    } while ( !stack.isEmpty() || p != NULL );
    return sum;
} 

/******************************************************************************/
bool BinarySearchTree::completeTree()
{
   completeTree(root);
}
/******************************************************************************/
bool BinarySearchTree::completeTree(BinaryNode * rootNode)
{     
     
    Stack<BinaryNode* > stack; 
    BinaryNode* p;
    p = root;
    bool balance;
    do
    {
     while( p != NULL )
        {
            stack.push( p );
            if(p->left!=NULL && p->right!=NULL || p->left==NULL && p->right==NULL)
               balance = true;
            else return false;
            p = p->left;
        }
     
     if( !stack.isEmpty() )
	 {
        	p = stack.pop();
        	p = p->right; 
	 }
	} while ( !stack.isEmpty() || p != NULL );
}
/******************************************************************************/

bool BinarySearchTree::similarTree(BinarySearchTree *tree1, BinarySearchTree *tree2)
{
    bool similar=false;
    Stack<BinaryNode* > stack, stack1;
    BinaryNode* p,* q;
    int temp1, temp2;
    p = tree1->root;
    q = tree2->root;
    
    do
    {
        while( p != NULL || q!=NULL)
        {
         if(p!=NULL)
           {
            stack.push( p );
            p = p->left;
           }
         if(q!=NULL)
           {  
            stack1.push(q);
            q = q->left;
           } 
        }
        // at this point, left tree is empty 
	 if( !stack.isEmpty())// || !stack1.isEmpty())
	 {
        	p = stack.pop();
        	temp1=p->number;
            p=p->right;
     }
     
     if( !stack1.isEmpty())
	 {
        	q = stack1.pop();
        	temp2=q->number;
        	q=q->right;
 	 }
    
    if(temp1==temp2)
      similar=true;
    else
      similar=false;
    } while ( !stack.isEmpty() || p != NULL ||!stack1.isEmpty() || q!=NULL);
    return similar;
  
}


