tree representation and node deletion

tree.c

// creates a binary search tree
#include<stdio.h>
#include<stdlib.h>

typedef struct node{       
	struct node* left;
	struct node* right;
	int value;
}treenode;

int add_node(treenode**tree, int value);
treenode* get_min(treenode*tree);
treenode* get_node();
treenode* get_max(treenode*tree);
treenode* search_value(treenode*tree,int searchvalue);
void delete_node(treenode**tree,treenode* victim);
void intrav(treenode*tree);
void pretrav(treenode*tree);
void posttrav(treenode*tree);
treenode* get_parent(treenode*tree, treenode*selected);

//returns the address of the newly created node.
treenode* get_node(){
	treenode* x = (treenode*)malloc(sizeof(struct node));
	x->right = NULL;
	x->left = NULL;
	x->value = -1;
	return x;
}

//add the new node in the tree , returns 0 in case of success.
int add_node(treenode**tree, int value)  {   
	// TODO: implement recursive version of add_node
	int left;  // will decide the direction
	left=0;
	
	treenode* x = get_node(); // get the pointer to allocated memory
	x->value = value;
	// 2 cases arises
	// if it is the first node to be entered
	if(*tree==NULL)
	{
		*tree = x;
		return 0;
	}
	else // if not we will have to traverse
	{
		treenode* trav = *tree;
		treenode* follow = *tree; // will follow the trav
		while(trav!=NULL)
		{
			if(x->value<trav->value)
			{    // traversing left                
				follow = trav;
				left = 1;
				trav= trav->left;
				continue;
			}
			else
			{
				follow = trav;
				left = 0;
				trav = trav->right;
				continue;
			}
		}
		if(left)
		follow->left = x;
		else
		follow->right= x;
		return 0;
	}
	return 1;
}

treenode* get_min(treenode*tree){
	//returns the pointer to the node with minimum value;
	// returns NULL in case of problem
	treenode*min = tree;
	treenode*trav = tree;
	if(tree==NULL)   // handle null tree case
	return NULL;
	else
	{
		while(trav!=NULL)
		{
			min = trav;
			trav = trav->left;
		}
		return min;
	}
	
	return NULL;
		
}

treenode* get_max(treenode*tree){
	//returns the pointer to the node with maximum value;
	// returns NULL in case of problem
	treenode*max = tree;
	treenode*trav = tree;
	if(tree==NULL)   // handle null tree case
	return NULL;
	else
	{
		while(trav!=NULL)
		{
			max = trav;
			trav = trav->right;
		}
		return max;
	}
	
	return NULL;
}

treenode* search_value(treenode*tree,int searchvalue){
	treenode* trav = tree;
	while(trav!=NULL)
	{
		if(trav->value==searchvalue)   // made mistake in == vs =
		return trav;
		if(trav->value>searchvalue)
		trav = trav->left;
		else
		trav = trav->right;
		if(trav->value==searchvalue)
		return trav;
	}
	return NULL;
}

void delete_node(treenode**tree,treenode* victim){
	// return 1 in case of non successfull
/*
 * handle the root case in all the cases
 * need pointer to parent of the node to be deleted 
 * recursion in last case .
 * 
 * */
	treenode*left=NULL;
	treenode*right=NULL;
	//printf("\n%d\n",(victim->right)->value);
	if((*tree==NULL) || (victim==NULL))
	return ;  // tree is null or victim is null
	else   // now we have to work 
	{
		if(victim==NULL)return ;  // tree exist but victim not
		else  // real work starts
		{
			left = victim->left;
			right=victim->right;
			//printf("%p",get_parent(*tree,victim));
			treenode* parent = get_parent(*tree,victim);
			if((left==NULL)&&(right==NULL)) // case for leaf node
			{
				if(parent==NULL) // trying to delete the root node itself
                {
					*tree = NULL;
					printf("root node deleted");
					return;
				}
				if(parent->left==victim)
				parent->left = NULL;
				else
				parent->right = NULL;
				printf("case 1");
				return;
			}
			else if(left==NULL)   // right tree exists 
			{
				if(parent==NULL) // root node case
				{
					*tree = victim->right;
					return;
				}
				if(parent->left ==victim) // to be deleted node is to the left of the parent
				{
					parent->left = victim->right; 
				}
				else
				parent->right = victim->right;
				printf("case 2 a");
				return;
				
			}
			else if(right==NULL)     // left subtree exists
			{
				if(parent==NULL)
				{
					*tree = victim->left;
					return ;
				}
				if(parent->left ==victim)
				parent->left = victim->left;
				else 
				parent->right = victim->left;
				printf("case 2 b");
			}
			else   // ok both the subtree exists, replace the deleted node's key with 
			{       //the next in inorder and than delete the inorder successor node with same function
				treenode* successor = get_min(victim->right);
				//printf("\n%d\n",(victim->right)->value);
				victim->value = successor->value;
				printf("case 3 ");
				delete_node(tree,successor);
			}
				
			
		}
	}
			
}

void intrav(treenode*tree){
	if(tree==NULL)
	return;
	intrav(tree->left);
	printf("%d ",tree->value);
	intrav(tree->right);
}

void pretrav(treenode*tree){
	//TODO: implement
}

void posttrav(treenode*tree){
	//TODO:implement
}

treenode* get_parent(treenode*tree, treenode*selected){
	treenode* trav = tree;
	treenode* follow = tree;
	if(tree==NULL||selected==tree)
	{
		//printf("\ntrying to access the parent of root\n");
		return NULL;
	}	
	else
	{
		while(trav!=selected)
		{
			while((trav!=NULL)&&(trav->value!=selected->value))
			{
				if(selected->value<trav->value)
				{ 
					follow = trav;
					trav = trav->left;
				}
				else
				{
					follow = trav;
					trav = trav->right;
				}
			}
			if(trav!=selected)
			{
				follow = trav;
				trav = trav->right;
			}
			
		}
		return follow;
	}
	return NULL;
}
				
int main()
{
	treenode* tree = NULL; // this will be the tree root pointer
	// I need to edit the tree pointer so will have to pass 
	// the address of the tree pointer.
	int input[15] = {15,7,50,2,12,25,75,1,4,8,14,20,40,60,80};
	//int input[3] = {2,3};
	int i;
	for(i=0;i<15;i++)
	add_node(&tree,input[i]);
	
	//printf("%d",(((tree->right)->left)->right)->value);
	//should print 40
	intrav(tree); //prints the tree in sorted order
	//printf("%d",get_max(tree)->value);
	//printf("%p",NULL);
	//printf("%d",get_parent(tree,((tree->left)->right)->left)->value);
	//printf("%d",search_value(tree,2)->value);
	//intrav(tree);
	delete_node(&tree,search_value(tree,50));
	printf("\n");
	intrav(tree);
	return 0;
}