//TREE.C@standard c library(*SCL*) by ASHISH TIWARI
/*
You may print, store code from this program for your personal,
noncommercial use. By accessing this code, you agree not to reproduce, distribute,
display or transmit information from this code in any form or by any means without
the permission of ASHISH TIWARI, with this exception: You may occasionally reproduce,
distribute, display or transmit an insubstantial portion of the information, for a
noncommercial purpose, to a limited number of individuals. ASHISH TIWARI does not warrant
the accuracy, completeness, timeliness, merchantability or fitness for a particular purpose
of the cose,though every care has been taken in making this code and has been compiled
on standard gcc compiler provided by GNU. ASHISH TIWARI shall not be liable for any
errors or omissions in the information or decisions made or actions taken in reliance
on the code.

"*SCL*" is a registered trademark of ASHISH TIWARI, IITKGP.
All contents of "*SCL*" is copyright ©2000-.... ,ASHISH TIWARI, IITKGP
unless otherwise noted. Reproduction in part or in whole without
permission is expressly prohibited.
*/
#include<stdio.h>
#include<stdlib.h>
#define search_item 7
struct tree{
int data;
struct tree* left;
struct tree* right;
};
typedef struct tree node;
node* parent;
node* add(node* root,int item);
void inorder(node* root);
void postorder(node* root);
void preorder(node* root);
node* search(node* start,int item);
void delete(node* start,int item);
main()
{
node* root;

node* search_node;
int item,i;
root=NULL;
parent=NULL;
search_node=NULL;
for(i=0;i<10;i++)
root=add(root,i);
inorder(root);
search_node=search(root,search_item);
printf("%d->%d\n",parent->data,search_node->data);
delete(root,7);
inorder(root);
printf("\n");
postorder(root);
printf("\n");
preorder(root);
}


node* add(node* root,int item)
{
if(root==NULL)
{
root=(node*)malloc(sizeof(node));
root->data=item;
root->left=NULL;
root->right=NULL;
}
else
{
if(item<=root->data)
root->left=add(root->left,item);
else
root->right=add(root->right,item);
}
return(root);
}


void inorder(node* root)//leftsubtree then node then right subtree
{
if(root==NULL)
return;
else
{
inorder(root->left);
printf("%d\n",root->data);
inorder(root->right);
}
}
void postorder(node* root)//first subtrees then node
{
if(root==NULL)
return;
else
{
postorder(root->left);
postorder(root->right);
printf("%d\n",root->data);
}
}

void preorder(node* root)//first node then its subtrees
{
if(root==NULL)
return;
else
{
printf("%d\n",root->data);
preorder(root->left);
preorder(root->right);
}
}


node* search(node* start,int item)
{
//if tree is empty
if(start==NULL)
{
printf("tree is empty\n");
return(start);
}
/*traverse tree in search of element*/
else
{
while(start!=NULL)
{
if(start->data==item)
return(start);
else
{
if(start->data>item)
{
parent=start;
start=start->left;
}
else
{
parent=start;
start=start->right;
}
}
}

}
printf("element not found\n");
return(NULL);
}


void delete(node* start,int item)
{
node* req;
node* xsucc;
req=NULL;
xsucc=NULL;
req=search(start,item);
//if req node is not found then how can v delete it?
if(req==NULL)
{
printf("so v can't delete\n");
exit(1);
}
//two children
if(req->left!=NULL && req->right!=NULL)
{
parent=req;
xsucc=req->right;
while(xsucc->left!=NULL)
{
parent=xsucc;
xsucc=xsucc->left;
}
req->data=xsucc->data;
req=xsucc;
}
//only leftchild
if(req->left!=NULL && req->right==NULL)
{
if(parent->left==req)
parent->left=req->left;
else
parent->right=req->right;

}
//only right child
if(req->right!=NULL && req->left==NULL)
{
if(parent->right==req)
parent->right=req->right;
else
parent->left=req->left;

}
//no child
if(req->right==NULL && req->left==NULL)
{
if(parent->right==req)
parent->right=req->right;
else
parent->left=req->left;

}
free(req);
return;
}