#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define true 1
#define false 0
#define log2(a) log((a))/log(2)

typedef struct node* nodeptr;

typedef struct node
{
        int val;
        nodeptr leftchild;
        nodeptr rightchild;
        int bf;
}node;

void insert(nodeptr *parent,int *unbalanced,int key);
void leftRotation(nodeptr *pparent,int *unbalanced);//..means if left subtree grows larger then rotate this left subtree
void rightrotation(nodeptr *,int *);//................vice versa
int height(node* node);
void inorder(node *proot);

int main(void)
{
    node *root,*cur;
    root=NULL;
    int balancedState=true;
    //int num[]={1,2,3,4,5,6,8,9,10,7};//..input series..{8,7,2,9},{8,7,2,9,10},{8,7,2,9,10,11}
    int num[]={10,9,8,7,6,5,3,2,1,4,15,14,16,12};
    int size=sizeof(num)/sizeof(int);
    int i=0;
    for(i=0;i<size;i++)
    {
                   printf("\nheight before insertion of %d is %d\n",num[i],height(root)-1);
                   insert(&root,&balancedState,num[i]);
                   printf("\n%d is inserted.\nHeight after insertion is: %d",num[i],height(root)-1);

                   printf("\n\n****************************************************");
    }

    printf("\n\nfinal height is: %d",height(root)-1);
    printf("\nno of nodes are %d.\nAnd log2(%d) is %f.",size,size,log2(size));
    printf("\nSo Height is almost equal to log2(%d))\n",size);
    printf("\noutput<inorder traversal of tree: ");
    if(root==NULL)
                  printf("\nnull");
    inorder(root);
    getch();
    //return 0;
}

void insert(nodeptr *parent,int *unbalanced,int key)
{
     if(!(*parent))
     {
                   //printf("mhere 1");
          node *newnode;
          newnode=(node *)malloc(sizeof(node));
          newnode->leftchild=newnode->rightchild=NULL;
          newnode->val=key;
          newnode->bf=0;
          *unbalanced=true;
          *parent=newnode;
          //printf("mhere 1");
          //return newnode;
     }
     else if(key<(*parent)->val)
     {
          //printf("\nm here2");
          insert(&(*parent)->leftchild,unbalanced,key);
          if(*unbalanced)
          {
             switch((*parent)->bf)
             {
              case -1: (*parent)->bf=0;
                       //printf("\nreset bf");
                       *unbalanced=false;
                       break;
              case 0: (*parent)->bf=1;
                      //printf("\nset bf");
                       break;
              case 1: leftRotation(parent,unbalanced);
                      //printf("\n**LEFT ROTATION DONE**\n");
                       break;////////////////////////////////////
              }
          }

     }
     else if(key>(*parent)->val)
     {
          //printf("m here3");
          insert(&(*parent)->rightchild,unbalanced,key);
          //printf("m here4");
          if(*unbalanced)
          {
           switch((*parent)->bf)
           {
              case 1: (*parent)->bf=0;
                        *unbalanced=false;
                        break;
              case 0: (*parent)->bf=-1;
                        break;
              case -1: //printf("going to rightrOTATE");
                       rightrotation(parent,unbalanced);
                       //printf("\n**RIGHT ROTATION DONE**\n");
                       break;
           }
        }
        else
        {
            *unbalanced=false;
            //printf("the key is already in the tree");
        }
     }
}

void leftRotation(nodeptr *pparent,int *unbalanced)
{
     nodeptr child,grandchild;
     child=(*pparent)->leftchild;
     if(child->bf==1)
     {
                     printf("\nsimple left rotation.");
        (*pparent)->leftchild=child->rightchild;
        child->rightchild=(*pparent);
        (*pparent)->bf=0;
        (*pparent)=child;
     }
     else
     {
         printf("\nDOUBLE leftROTATION");
      grandchild=child->rightchild;
      child->rightchild=grandchild->leftchild;
      grandchild->leftchild=child;
      (*pparent)->leftchild=grandchild->rightchild;
      grandchild->rightchild=*pparent;
      switch(grandchild->bf)
        {
             case 1:(*pparent )->bf=-1;child->bf=0;break;
             case 0:(*pparent)->bf=child->bf=0;break;
             case -1:(*pparent)->bf=0;
                      child->bf=1;
             break;
        }
        *pparent=grandchild;
     }
     (*pparent)->bf=0;
     *unbalanced=false;
     return;
}

void rightrotation(nodeptr *pparent,int *unbalanced)
{
     nodeptr child,grandchild;
     child=(*pparent)->rightchild;
     if(child->bf==-1)
     {
                      printf("\nSIMPLE RIGHTROTATION");
         (*pparent)->rightchild=child->leftchild;
         child->leftchild=*pparent;
         (*pparent)->bf=0;
         (*pparent)=child;
     }
     else
     {
         printf("\nDOUBLE rightROTATION.");
         grandchild=child->leftchild;
         child->leftchild=grandchild->rightchild;
         grandchild->rightchild=child;
         (*pparent)->rightchild=grandchild->leftchild;
         grandchild->leftchild=*pparent;
         switch(grandchild->bf){
         case 1:(*pparent)->bf=-1;
                 child->bf=0;
                 break;
         case 0: (*pparent)->bf=child->bf=0;
                 break;
         case -1:(*pparent)->bf=0;
                  child->bf=1;break;
         }
         *pparent=grandchild;
     }
     (*pparent)->bf=0;
     *unbalanced=false;
     return;
}

int height(node* node)
{
   if (node==NULL)
       return 0;
   else
   {
       ///* compute the depth of each subtree
       int lDepth = height(node->leftchild);
       int rDepth = height(node->rightchild);

       ///* use the larger one
       if (lDepth > rDepth)
           return(lDepth+1);
       else return(rDepth+1);
   }
}

void inorder(node *proot)
{
     if(proot==NULL)return;
     inorder(proot->leftchild);
     printf("\nkey:%3d\tbalancefactor:%3d",proot->val,proot->bf);
     inorder(proot->rightchild);

}