Thread: Help with delete - Binary search tree

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( &currentNode );
		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( &currentNode->leftChild );
		printf("%d\t", currentNode->data);
		displayTree( &currentNode->rightChild );
	}
}

Thanks