//=======================================================================================================
//Finished 9th Nov 2011 3:55 pm
//code by: shashi kant

//=======================================================================================================
#include<stdio.h>
#include<stdlib.h>
# define TREESIZE 14
#define nodeDel 10


struct node                                            //tree node structure ::NOTE: PARENT Node can be stored ...looks more feasible
{
  int data;
  struct node *rnode;
  struct node *lnode;
};


typedef struct node* Node;
int count_node=0;
int count_leave=0;


//function  declarations
void count_nodes(Node root);
void count_leaves(Node root);
//Node delete_dataNode(Node root,int data);
Node deleteNode(Node root,int data);   //my version working
int max(int a,int b);
int maxSumOfTreeFromANode(Node root);
int height(Node root);
Node minimum(Node root,Node returnParent);
Node binaryInsert(Node root,int data);
Node binarySearch_iterative(Node root ,int data);
Node maximum(Node root);
void Go_binarySearch_recursive(Node root ,int data);
int binarySearch_recursive(Node root ,int data);
void traverse_inorder(Node root);                       //for binary sort
void traverse_preorder(Node root);
void traverse_postorder(Node root);
void digraphOutput(Node root);
void printOutput(Node root,FILE *fp);
Node findParent(Node root,int data);



//function Implementations.....
Node binaryInsert(Node root,int data)                    //iterative definition
{
   Node prevnode,curnode=root;
   if(root==NULL)   //tree is empty
   {
     root=(Node)malloc(sizeof(struct node ));
     root->data=data;
     root->rnode=root->lnode=NULL;
     return root;
   }

   //else
   while(curnode!=NULL)
   {
     prevnode=curnode;
     curnode=(curnode->data < data)?curnode->rnode :curnode->lnode;         //binary decision
   }

   if(prevnode->data < data)               //on the right side
   {
     prevnode->rnode=(Node)malloc(sizeof(struct node));
     prevnode->rnode->data=data;
     prevnode->rnode->rnode=NULL;
     prevnode->rnode->lnode=NULL;
   }
   else if(prevnode->data > data)                   //on the left side
   {
     prevnode->lnode=(Node)malloc(sizeof(struct node));
     prevnode->lnode->data=data;
     prevnode->lnode->rnode=NULL;
     prevnode->lnode->lnode=NULL;
   }
   else printf("Data already present in the tree ::  \"NO copying of Data Protocol\" \n");            //no copying allowed
   return root;
}


Node binarySearch_iterative(Node root ,int data)
{
  Node curnode=root,prevnode;
  if(root==NULL)           //empty tree
  {
    printf("Tree empty :no data in the tree\n");
    return NULL;
  }
  //else
  while(curnode!=NULL && curnode->data!=data)
  {
     prevnode=curnode;
     curnode=(curnode->data < data)?curnode->rnode :curnode->lnode;         //binary decision
  }
  if(curnode==NULL)
  {
    printf("Item not found \n");
    return NULL;
  }
  else if(curnode->data==data)
  {
    printf("Item found\n");
    return curnode;
  }
  return NULL;
}


void Go_binarySearch_recursive(Node root ,int data)
{
  int x=-1;
  x=binarySearch_recursive(root,data);
  if(x==0)printf("item not found \n");
}

int binarySearch_recursive(Node root ,int data)               //recursive definition
{
  int x=0;
  if(root!=NULL)
  {
    if(root->data == data){ printf("Item found \n");return 1;}
    else
        if(root->data < data)
           x=binarySearch_recursive(root->rnode,data);
        else
           x=binarySearch_recursive(root->lnode,data);
  }
 return x;
}




Node maximum(Node root)          //returns the node with maximum data value
{
  Node curnode=root;
  if(root==NULL)printf("Tree is empty");
  while(curnode->rnode!=NULL)curnode=curnode->rnode;
  printf("maximum node is %d",curnode->data);
  return curnode;
}


Node minimum(Node root,Node returnParent)    //returns the node with least value and stores the parent value in returnParent
{

  Node curnode=root;
  if(root==NULL)printf("Tree is empty");
  while(curnode->lnode!=NULL){returnParent=curnode ; curnode=curnode->lnode;}
  //printf("minimum node is %d \n",curnode->data);
  return curnode;

}

int height(Node root)
{
 if(root==NULL) return 0;
  return 1+max(height(root->rnode),height(root->lnode));
}

int max(int a,int b)
{
  return a>b?a:b;
}


//Finds out the Maximum sum of node values from root down to any Leaf
int maxSumOfTreeFromANode(Node root) {

}

void count_nodes(Node root)   //inorder way
{
  if(root!=NULL)
  {
    count_nodes(root->rnode);
    count_node++;
    count_nodes(root->lnode);
  }
}

void count_leaves(Node root)
{
   if(root!=NULL)
   {
     if(root->rnode==NULL && root->lnode==NULL) count_leave++;   //if both left and right subtrees are null it's a leaf
       count_leaves(root->rnode);
       count_leaves(root->lnode);
   }

}


//deletion my version
Node deleteNode(Node root,int data)
{
  Node curnode,parent;
  if(root == NULL)
  {
    printf("Error: Tree empty\n");
    return root;
  }



  curnode =root;
  while( curnode!=NULL && curnode->data!=data)
  {
    parent=curnode;
    curnode=(curnode->data < data)?curnode->rnode:curnode->lnode;
  }


  if(curnode==NULL)
  {
    printf("Error: item not found");
    return root;
  }

  //else if it's a leaf node
  if(curnode->lnode==NULL && curnode->rnode == NULL)
  {
    if(parent->data > curnode->data)parent->lnode=NULL;
    else parent->rnode=NULL;
    free(curnode);
    return root;
  }

//case when it has atleast a child
  if(curnode->lnode==NULL  && curnode->rnode!=NULL)
  {
    if(parent->data > curnode->data)parent->lnode=curnode->rnode;
    else parent->rnode=curnode->rnode;
    free(curnode);
    return root;
  }

   if(curnode->lnode!=NULL  && curnode->rnode == NULL)
  {
    if(parent->data > curnode->data)parent->lnode=curnode->lnode;
    else parent->rnode=curnode->lnode;
    free(curnode);
    return root;
  }

  //cas when both children are present
  else{
    //find successor and swap the values and delete node at successor position
    Node SuccNode,parent;
    int temp;
    SuccNode=minimum(curnode->rnode,parent);  //finding successor
    //parent=findParent(root,SuccNode->data);


    //if(parent->data > SuccNode->data)
      parent->lnode=NULL;  //unecessary check min element will be at left most end hence will be on left side of Parent
    //else parent->rnode=SuccNode->rnode;

    temp=curnode->data;
    curnode->data=SuccNode->data;
    SuccNode->data=temp;

    free(SuccNode);
    return root;

  }

}




//tree traversing tech
void traverse_inorder(Node root)
{
  if(root!=NULL)
  {
    traverse_inorder(root->lnode);
    printf("  %d",root->data);
    traverse_inorder(root->rnode);
  }
}


void traverse_preorder(Node root)
{
  if(root!=NULL)
  {
    printf("  %d",root->data);
    traverse_preorder(root->lnode);
    traverse_preorder(root->rnode);
  }
}


void traverse_postorder(Node root)
{
  if(root!=NULL)
  {
    traverse_postorder(root->lnode);
    traverse_postorder(root->rnode);
    printf("  %d",root->data);
  }
}

//end of traversal techniques


//Digraph output for Graphviz
void digraphOutput(Node root)
{
  FILE *fp;
  fp = fopen("mytree.dot","w");
  fprintf(fp,"digraph G { \n");
  fprintf(fp,"\"%d\";\n",root->data);  //print root first
  printOutput(root,fp);
  fprintf(fp,"}\n");
  fclose(fp);
}

void printOutput(Node root,FILE *fp)
{
  if(root!=NULL)
  {
    //fprintf(fp,"\"%s\"",root->data);
    //find out children  declare them and then the edge
    if(root->lnode!=NULL)
    {
      fprintf(fp,"\"%d\";\n",root->lnode->data);
      fprintf(fp,"\"%d\"-> \"%d\";\n",root->data,root->lnode->data);
    }
    if(root->rnode!=NULL)
    {
      fprintf(fp,"\"%d\";\n",root->rnode->data);
      fprintf(fp,"\"%d\"-> \"%d\";\n",root->data,root->rnode->data);
    }
    printOutput(root->lnode,fp);
    printOutput(root->rnode,fp);
  }

}






Node findParent(Node root,int data)
{
   Node curnode =root,parent;
  while( curnode!=NULL && curnode->data!=data)
  {
  //  printf("fine 4\n");
    parent=curnode;
    printf("%d \n",curnode->data);
    curnode=(curnode->data < data)?curnode->rnode:curnode->lnode;
  }
  printf("%d <-",curnode->data);
  printf("%d parent \n \n",parent->data);
  return parent;
}

//the main function....
int main()
{
   Node root=NULL;
   int count=0;
   int fillList[TREESIZE]={18,10,20,4,15,19,22,1,8,11,41,21,23,58};


   for(count=0;count<TREESIZE;count++)
   {
     root=binaryInsert(root,fillList[count]);
   }

   root=deleteNode(root,11);  //optional stuff only to check if deletion Logic works
   printf("\n\n Max sum of tree = %d\n\n",maxSumOfTreeFromANode(root));
   digraphOutput(root);
   traverse_inorder(root);
   printf("\n");
   return 0;
}