Help with delete - Binary search tree

This is a discussion on Help with delete - Binary search tree within the C Programming forums, part of the General Programming Boards category; I need help with the delete operation on a binary search tree. The delete operation works fine for leaf nodes ...

  1. #1
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53

    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
    Last edited by lazyme; 03-20-2010 at 07:01 PM. Reason: fixed the code slightly

  2. #2
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    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)!!!!!!!! */

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Quote Originally Posted by claudiu View Post
    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?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by iMalc View Post
    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?
    You are correct. That doesn't even make any sense to me now that I read it again. Sorry for any confusion created as a result of my bad advice. I actually have been programming in C for a while now, it's probably the fatigue of working on a deadline that made me state such silly things.

  6. #6
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    I found there was an error with my relinking and the nodes with one children were not getting relinked at all.

    I managed to fix some bugs and the delete works fine now for nodes with 1 child and 2 children.

    Code:
    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)->rightChild;
    		(*nodeToDelete)->data = tempNode->data;
    		(*nodeToDelete)->rightChild = tempNode->rightChild;
    		free( tempNode );
    	}
    	else if( (*nodeToDelete)->rightChild == NULL )
    	{
    		tempNode = (*nodeToDelete)->leftChild;
    		(*nodeToDelete)->data = tempNode->data;
    		(*nodeToDelete)->leftChild = tempNode->leftChild;
    		free( tempNode );
    	}
    	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);
    	}
    }
    However, there are still some bug. When i delete the final root node and try to display the tree, the program crashes.

    Also sometimes deleting one node causes a whole chain of nodes to detach from the tree.

  7. #7
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    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?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  8. #8
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    ^^
    Thanks for pointing out the mistake. The delete works just fine now.

    Code:
    else if( (*nodeToDelete)->leftChild == NULL )
    	{
    		tempNode = (*nodeToDelete)->rightChild;
    		(*nodeToDelete)->data = tempNode->data;
    		(*nodeToDelete)->rightChild = tempNode->rightChild;
    		(*nodeToDelete)->leftChild = tempNode->leftChild;
    		free( tempNode );
    	}
    I think it would have been easier if I had the parent of the node I wanted to delete and simply linked it as parentNode->leftChild = (*nodeToDelete)->rightChild

    Also, 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.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    [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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Apprentice
    Join Date
    Oct 2006
    Location
    LA
    Posts
    53
    The delete works fine now for every node other than the last node in the tree. Even for the last node, the node is deleted however the memory pointed to by the rootNode struct is freed.

    For the last node when I do

    Code:
    tempNode = *nodeToDelete;
    		*nodeToDelete = NULL;
    		free( tempNode );
    The *rootNode variable is no longer accessible and in the displayTree() function when the condition if( *rootNode != NULL ) is checked, it throws an exception.

    How can I get around this problem?

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Binary Search Tree
    By dookie in forum C++ Programming
    Replies: 5
    Last Post: 05-10-2008, 04:35 PM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 08:11 AM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21