#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

class node
{
      public:
      int info;
      node *parent;
      node *left;
      node *right;

      node();
};

node :: node()
{
     left = NULL;
     right = NULL;
}

class tree : node
{
      public:
      tree();
      ~tree();

      node *root;
      node *aux;

      void menu();

      private:
      void destruct(node*);
      bool insert_new(node*,int);
      bool remove(node*,int);
      int count(node*,int);
      node* search(node*,int);
      void print(node*);
      node* predecessor(node*);
      node* successor(node*);

};

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

void tree :: destruct(node *root)
{
     aux = root;

     if (aux != NULL)
        {
         if (aux->left != NULL)
            destruct(aux->left);
         if (aux->right != NULL)
            destruct(aux->right);

         delete aux;
        }

}

tree :: ~tree()
{
     destruct(root);
}

int tree :: count(node* aux, int cont)
{
    if(aux != NULL)
    {
        cont++;
        cont = count(aux->left, cont);
        cont = count(aux->right, cont);
    }
    return cont;
}


bool tree :: insert_new(node *aux, int value)
{
     node *data;

     if (aux == NULL)           // case 1: tree is empty
        {
         data = new node;
         data->info = value;
         data->parent = NULL;
         root = data;
         return true;
        }
     else
         {
          if (value > aux->info)                 // case 2: value is greater than current node
             {
              if (aux->right != NULL)
                 insert_new(aux->right, value);
              else
                  {
                   data = new node;
                   data->info = value;
                   aux->right = data;
                   data->parent = aux;
                   return true;
                   }
              }

          if (value < aux->info)                  // case 3: value is smaller than current node
             {
              if (aux->left != NULL)
                 insert_new(aux->left,value);
              else
                  {
                   data = new node;
                   data->info = value;
                   aux->left = data;
                   data->parent = aux;
                   return true;
                   }
              }
          }

}

void tree :: print(node *aux)   //in-order traversal
{
     if (aux == NULL)
        printf("tree is empty.");
     else
         {
          if (aux->left != NULL)
             print(aux->left);

          printf(" %d ",aux->info);

          if (aux->right != NULL)
             print(aux->right);

          }
}


node* tree :: search(node *aux, int value)
{

     if (aux == NULL)                     // case 1: no elements in tree
        {
         printf("tree is empty.");
         getch();
         return NULL;
         }

     if (aux->info == value)               // case 2: value searched is the root
        {
        printf("value %d found, it is the root",value);
        return aux;
        }

     if (value > aux->info)
        { printf("e maior que %d\n",aux->info);
          if (aux->right!= NULL)
             {printf("proximo a direita nao e nulo\n");
              if (aux->right->info == value)       // value searched is in right sub-tree
                 {
                  printf("value %d found, father is %d",value,aux->info);
                  getch();
                  return aux;
                  }
              else

                   if (value > aux->right->info || value < aux->right->info)
                      search(aux->right, value);
                   else
                       {
                       printf("value %d not found.",value);
                       getch();
                       return NULL;
                       }


              }
              else   //aux->right == NULL
                  {
                  printf("value %d not found.",value);
                  getch();
                  return NULL;
                  }
          }

     if (value < aux->info)
        {printf("e menor que %d\n",aux->info);
         if (aux->left != NULL)
            {printf("proximo a esquerda nao e nulo\n");
             if (aux->left->info == value)
                {
                 printf("value %d found, father is %d",value,aux->info);
                 getch();
                 return aux;
                 }
             else

                  if (value < aux->left->info || value > aux->left->info)
                     search(aux->left, value);


             }
             else //aux->left == NULL
                  {
                   printf("value %d not found.",value);
                   getch();
                   return NULL;
                  }
         }


} //end of function

void tree :: menu()
{
     printf("\n\n\t\t\t[data structures] :: binary search tree\n\n");

    int op;
    int value;

    printf("\n\n\tenter the desired option:");

    printf("\n\n\t %c1: insert a node in the tree.",175);
    printf("\n\t %c2: remove a node from the tree",175);
    printf("\n\t %c3: show tree (in-order traversal)",175);
    printf("\n\t %c4: search for a node",175);
    printf("\n\t %c5: count nodes",175);
    printf("\n\t %c6: quit",175);




    while (op != 6)
          {
          printf("\n\n\t\t%c",175);
           scanf("%d",&op);

           switch (op)
                  {
                   case 1: printf("\n\n\t\tenter the desired number to insert in the tree.");
                           printf("\n\n\t\t%c ",175);
                           scanf("%d",&value);
                           insert_new(root, value);
                           system("cls");
                           menu();
                           break;
                   case 2: printf("\n\n\t\tenter the desired number to remove from the tree.");
                           printf("\n\n\t\t%c ",175);
                           scanf("%d",&value);
                           remove(root,value);
                           system("cls");
                           menu();
                           break;
                   case 3: print(root);
                           getch();
                           system("cls");
                           menu();
                           break;
                   case 4: printf("\n\n\t\tenter the desired number to be searched.");
                           printf("\n\n\t\t%c ",175);
                           scanf("%d",&value);
                           search(root, value);
                           getch();
                           system("cls");
                           menu();
                           break;
                   case 5: printf("%d",count(root,0));
                   case 6: exit(0);
                   default: system("cls");
                            menu();
                   }
           }

     }

node* tree :: predecessor(node *start) //predecessor is the right-most node on the left sub-tree
{
      // start must be the child on the left of the node whose predecessor is being looked for

      if (start->right != NULL)
         return predecessor(start->right);
      else
          return start;
}

node* tree :: successor(node *start) //successor is the left-most node on the right sub-tree
{
      // start must be the child on the right of the node whose successor is being looked for

      if (start->left != NULL)
         return successor(start->left);
      else
          return start;

}

bool tree :: remove(node* address,int value)
{
     aux = search(address,value);   //receives address from father of node to be removed
     printf("%d",aux->info);
     //return 0;

     if (aux == NULL)           // case 1: tree is empty
        return false;

    else

    if (aux->info == value)     // case 2: value to be removed is the root
       {
        if (aux->right == NULL && aux->left == NULL) // root has no children
           {
            delete aux;
            root = NULL;
            return true;
            }

        if (aux->right == NULL && aux->left != NULL) // root has a child in the left sub-tree
           {
            root = aux->left;
            delete aux;
            }

        if (aux->right != NULL && aux->left == NULL) // root has a child in the right sub-tree
           {
            root = aux->right;
            delete aux;
            }

        if (aux->right != NULL && aux->left != NULL) // root has children on both nodes
           {

            node *temp = successor(aux->right);
            printf("sucessor e' %d",temp->info);getch();

            int pivot = temp->info;
            aux->info = pivot;  // copy value of successor to node to be removed
            printf("\npivot e' %d",pivot);

            remove(temp->parent,pivot); // call function recursively to remove the same node but in a different sub-tree
            }
        }

     else
         {
          if (value > aux->info)        // case 2: node to be removed is in right sub-tree
             {
              if (aux->right->right == NULL && aux->right->left == NULL)   //node has no children
                 {
                  delete aux->right;
                  aux->right = NULL;
                  return true;
                  }

              else

              if (aux->right->right == NULL && aux->right->left != NULL) // node has a child in the left sub-tree
                 {
                  node *temp = aux->right;     // store the child of the node to be removed
                  aux->right = aux->right->left;  // point the father to the child of the node to be removed
                  delete temp;
                  return true;
                  }

              else

              if (aux->right->right != NULL && aux->right->left == NULL) // node has a child in the right sub-tree
                 {
                  node *temp = aux->right;
                  aux->right = aux->right->right;
                  delete temp;
                  return true;
                  }

              if (aux->right->right != NULL && aux->right->left != NULL) // node has children on both sub-tress
                 {
                  node *temp = successor(aux->right);
                  printf("sucessor e' %d",temp->info);getch();

                  int pivot = temp->info;
                  aux->info = pivot;  // copy value of successor to node to be removed
                  printf("\npivot e' %d",pivot);

                  remove(temp->parent,pivot); // call function recursively to remove the same node but in a different sub-tree
                  }


             } // end of value > aux->info

         if (value < aux->info) // case 4: node to be removed is in left sub-tree
            {
             if (aux->left->left == NULL && aux->left->right == NULL) // node has no children
                {
                 delete aux->left;
                 aux->left = NULL;
                 return true;
                 }

             else

             if (aux->left->right != NULL && aux->left->left == NULL)   // node has a child in right sub-tree
                {
                  node *temp = aux->left;     // store the child of the node to be removed
                  aux->left = aux->left->right;  // point the father to the child of the node to be removed
                  delete temp;
                  return true;
                }

             else

             if (aux->left->right == NULL && aux->left->left != NULL)  // node has a child in left sub-tree
                {
                  node *temp = aux->left;     // store the child of the node to be removed
                  aux->left = aux->left->left;  // point the father to the child of the node to be removed
                  delete temp;
                  return true;
                }

             if (aux->left->right != NULL && aux->left->left != NULL) // node has children on both sub-tress
                 {
                  node *temp = successor(aux->right);
                  printf("sucessor e' %d",temp->info);getch();

                  int pivot = temp->info;
                  aux->info = pivot;  // copy value of successor to node to be removed
                  printf("\npivot e' %d",pivot);

                  remove(temp->parent,pivot); // call function recursively to remove the same node but in a different sub-tree
                  }


            } //end of value < aux->info
     }

}

int main (void)
{

 tree bst;

 bst.menu();

 system("pause>null");

 return 0;

}