I need help with the delete operation on a binary search tree. The delete operation works fine for leaf nodes and nodes with one child. However, it does not work fine with nodes with 2 childs.
Here's the code
Code:
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *leftChild;
struct node *rightChild;
};
int insertNode( struct node**, int );
void displayTree( struct node** );
int findNode( struct node**, int );
int deleteNode( struct node**, int );
void deleteFromTree( struct node** );
int main()
{
int flag = 1;
int choice = 0;
int retVal = 0;
int nodeValue;
struct node *rootNode = NULL;
printf("\n\n");
while( flag )
{
printf("\n1 : Insert element in tree");
printf("\n2 : Display elements in tree");
printf("\n3 : Find element in tree");
printf("\n4 : Delete element from tree");
printf("\n5 : Exit");
printf("\n\nPlease enter a choice : ");
scanf_s("%d", &choice);
switch( choice )
{
case 1 :printf("Enter the value to insert : ");
scanf_s("%d", &nodeValue);
retVal = insertNode( &rootNode, nodeValue );
break;
case 2 :displayTree( &rootNode );
break;
case 3 :printf("Enter the element to find : ");
scanf_s("%d", &nodeValue);
retVal = findNode( &rootNode, nodeValue );
if(retVal == 1)
printf("\nFound!!\n");
else
printf("\nNot Found!!\n");
break;
case 4 :printf("Enter the element to delete : ");
scanf_s("%d", &nodeValue);
retVal = deleteNode( &rootNode, nodeValue );
if(retVal == 1)
printf("\nDeleted!!\n");
else
printf("\nNot Found!!\n");
break;
case 5 :flag = 0;
break;
default : printf( "Please insert a valid choice" );
}
}
return 0;
}
int findNode( struct node **rootNode, int nodeValue )
{
struct node* currentNode = *rootNode;
int found = 0;
while(!found && currentNode != NULL)
{
if( currentNode->data == nodeValue )
return found = 1;
else if( currentNode->data > nodeValue )
currentNode = currentNode->leftChild;
else
currentNode = currentNode->rightChild;
}
return found;
}
int deleteNode( struct node **rootNode, int nodeValue )
{
struct node* currentNode = *rootNode;
struct node* trailNode = NULL;
int found = 0;
while(!found && currentNode != NULL)
{
if( currentNode->data == nodeValue )
found = 1;
else
{
trailNode = currentNode;
if( currentNode->data > nodeValue )
currentNode = currentNode->leftChild;
else
currentNode = currentNode->rightChild;
}
}
if(found == 1)
{
if( trailNode == NULL )
deleteFromTree( ¤tNode );
else if( trailNode->data > nodeValue )
deleteFromTree( &trailNode->leftChild );
else
deleteFromTree( &trailNode->rightChild );
}
return found;
}
void deleteFromTree( struct node **nodeToDelete )
{
struct node* tempNode = NULL;
struct node* currentNode = *nodeToDelete;
struct node* trailNode = NULL;
if( (*nodeToDelete)->leftChild == NULL && (*nodeToDelete)->rightChild == NULL )
{
tempNode = *nodeToDelete;
*nodeToDelete = NULL;
free( tempNode );
}
else if( (*nodeToDelete)->leftChild == NULL )
{
tempNode = *nodeToDelete;
*nodeToDelete = (*nodeToDelete)->rightChild;
free( tempNode );
}
else if( (*nodeToDelete)->rightChild == NULL )
{
tempNode = *nodeToDelete;
*nodeToDelete = (*nodeToDelete)->leftChild;
free( tempNode );
}
else
{
currentNode = currentNode->leftChild;
while( currentNode != NULL )
{
trailNode = currentNode;
currentNode = currentNode->rightChild;
}
(*nodeToDelete)->data = trailNode->data;
tempNode = trailNode;
trailNode = trailNode->leftChild;
free(tempNode);
}
}
int insertNode( struct node **rootNode, int nodeValue )
{
struct node *newNode = NULL;
struct node *currentNode = NULL;
struct node *trailNode = NULL;
int retVal = 0;
newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = nodeValue;
newNode->leftChild = NULL;
newNode->rightChild = NULL;
if(*rootNode == NULL)
{
*rootNode = newNode;
retVal = 1;
}
else
{
currentNode = currentNode->leftChild;
printf( "\ncurrentnode data = %d", currentNode->data );
while( currentNode->rightChild != NULL )
{
trailNode = currentNode;
currentNode = currentNode->rightChild;
}
(*nodeToDelete)->data = currentNode->data;
if( trailNode == NULL )
(*nodeToDelete)->leftChild = currentNode->leftChild;
else
trailNode->rightChild = currentNode->leftChild;
free(currentNode);
}
return retVal;
}
void displayTree( struct node **rootNode )
{
struct node* currentNode = NULL;
if( *rootNode != NULL )
{
currentNode = *rootNode;
displayTree( ¤tNode->leftChild );
printf("%d\t", currentNode->data);
displayTree( ¤tNode->rightChild );
}
}
Thanks