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

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)!!!!!!!! */

---

Quote:

---

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.

Quote:

---

Originally Posted by iMalc

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.

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.

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?

^^
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.

[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.

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?

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.