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

Originally Posted by claudiu

To be honest I don't think any of the deletes work.

You are doing:

Code:

tempNode = *nodeToDelete; /* tempNode is now pointing to nodeToDelete */
*nodeToDelete = NULL; /* tempNode is also now pointing to NULL*/
free(tempNode); /* free(NULL)!!!!!!!! */

No, that code does not do what you are thinking. nodeToDelete does not point to tempNode and thus cannot cause tempNode to become NULL on the second line above. Thus it would not always be freeing NULL.
You're still new to C, and probably haven't written a binary tree deletion function yourself yet. Wait until you've done so before you try helping others to do the same huh?

It looks like in the two-children case, you're trying to move the data instead of relinking the nodes. Don't be inconsistent, they should all be done the same way. Once you've found the rightmost node of the leftmost subtree, detach that node from where it is in the tree, then link that node in where the one you want to delete was.

The thing that makes it much easier is if you make removeRightmostFromTree a separate function, and get that fully working on its own before you use it from within the deleteFromTree.

Code:

else if( (*nodeToDelete)->leftChild == NULL )
	{
		tempNode = (*nodeToDelete)->rightChild;
		(*nodeToDelete)->data = tempNode->data;
		(*nodeToDelete)->rightChild = tempNode->rightChild;
		free( tempNode );
	}

what about tempnode->leftchild? you just loose it?

[QUOTE=lazyme;931500Also, after deleting the last node of the binary tree, I get an exception when I try to print the tree. I know this is because the memory has been freed but is there a way I can avoid this exception.[/QUOTE]No, it can only mean that your delete function is still broken. I don't have time to help now, but you could try my earlier advice.

Oh, so you're using a sentinel node and it's getting deleted?
Maybe you could add special checks for the sentinel node. Hmm I guess that would increase the parameter counts somewhere.
I don't have this problem in my own tree implementations. Perhaps I'll make them available in my website.