Binary Search Tree

bst.c

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

struct bst
{
	struct bst *left,*right;
	int val;
};

struct bst* makenode(int);
struct bst* successor(struct bst*);
void insert(struct bst**,struct bst*);
void freetree(struct bst*);
void inorder(struct bst*);
int delete(struct bst**,int);
struct bst* search(struct bst*,int);
struct bst* findparent(struct bst*,struct bst*);


int main()
{
	struct bst* root=NULL;
	int key,choice;
	FILE *fp;
	fp=fopen("input","r");
	fscanf(fp,"%d",&key);
	while(!feof(fp))
	{
		struct bst* newnode=makenode(key);
		insert(&root,newnode);
		fscanf(fp,"%d",&key);
	}
	fclose(fp);
	do
	{
		printf("\nMENU\n1.INSERT\n2.DELETE\n3.INORDER\n4.EXIT");
		printf("\nENTER YOUR CHOICE(1/2/3/4):");
		scanf("%d",&choice);
		switch(choice)
		{
			case 1:	printf("\nENTER KEY:");
					scanf("%d",&key);
					insert(&root,makenode(key));
					printf("\nNEW NODE INSERTED");
					break;					
			case 2: printf("\nENTER KEY:");
					scanf("%d",&key);
			 		int success=delete(&root,key);
					if(success)
						printf("\nNODE SUCCESSFULLY DELETED FROM TREE");
					else
						printf("\nDELETION UNSUCCESSFUL");
					break;
			case 3:	inorder(root);
					break;
			case 4: freetree(root);
					break;
			default:printf("\nWRONG CHOICE");
					break;
		}
	}
	while(choice!=4);
	return 0;
}
				
void insert(struct bst** root,struct bst* newnode)
{
	if(*root==NULL)
		*root=newnode;
	else if((*root)->val>newnode->val)
		insert(&((*root)->left),newnode);
	else
		insert(&((*root)->right),newnode);		
}

void inorder(struct bst* root)
{
	if(root!=NULL)
	{
		inorder(root->left);
		printf("%d ",root->val);
		inorder(root->right);
	}
}

struct bst* successor(struct bst* node)
{
	if(node!=NULL)
		node=node->right;
	while(node!=NULL)
	{
		if(node->left==NULL)
			return node;
		else 
			node=node->left;
	}
	return node;
}		

struct bst* makenode(int key)
{
	struct bst* newnode=malloc(sizeof(struct bst));
	newnode->val=key;
	newnode->left=newnode->right=NULL;
	return newnode;
}

void freetree(struct bst* root)
{
	if(root!=NULL)
	{
		freetree(root->left);
		freetree(root->right);
		free(root);
	}
}

struct bst* search(struct bst *root,int key)
{
	if(root!=NULL)
	{
		if(root->val==key)
			return root;
		else if(root->val>key)
			return(search(root->left,key));
		else
			return(search(root->right,key));
	}
	else
		return root;
}

struct bst* findparent(struct bst* root,struct bst* temp)
{
    if(root==temp)
		return NULL;
	while(root!=NULL)
	{
		if(root->val>temp->val)
		{
			if(root->left!=NULL)
			{
				if(root->left->val==temp->val)
					return root;
				root=root->left;
			}
		}
		else
		{
			if(root->right!=NULL)
			{
				if(root->right->val==temp->val)
					return root;
				root=root->right;
			}
		}
	}	
	return NULL;	
}
		
int delete(struct bst** root,int key)
{
	struct bst *find=search(*root,key);
	if(find==NULL)
		return 0;
	else
	{
		if(find->left==NULL&&find->right==NULL)
		{
			if(find==*root)
				free(find);
			else
			{
				struct bst *parent=findparent(*root,find);
				if(parent->left!=NULL)
					if(parent->left==find)
						parent->left=NULL;
				if(parent->right!=NULL)
					if(parent->right==find)
						parent->right=NULL;
				free(find);
			}
		}
		else if(find->left!=NULL&&find->right==NULL)
		{
			struct bst* save=find->left;
			find->val=find->left->val;
			find->right=find->left->right;
			find->left=find->left->left;
			free(save);
		}
		else if(find->right!=NULL&&find->left==NULL)
		{
			struct bst* save=find->right;
			find->val=find->right->val;
			find->left=find->right->left;
			find->right=find->right->right;
			free(save);
		}
		else
		{
			struct bst* heir=successor(find);
			int key=heir->val;
			if(delete(root,key))
				find->val=key;
		}			
	}						
	return 1;
}

gistfile1.txt

6
4
8
2
5
7
9
1
3

For deleting nodes with two children the logic that a successor will not have a left child is used
save successors key, delete successor using the same function, copy successors value to the node to be deleted