Thread: Code for deleting a tree node not working

Hello,

I've come on here as a last resort for help as to why my code for deleting a tree doesn't work . Sometimes I get seg fault and sometimes it deletes extra nodes... Could someone please take a look at my code and let me know what's wrong?

I've been scratching my head for a week. The logic seems right but something's missing...

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct treeNode {
   struct treeNode *leftPtr;  /* pointer to left subtree */
   int data; /* node value */
   int height;
   struct treeNode *rightPtr; /* pointer to right subtree */
};

typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;

TreeNodePtr searchPar(TreeNodePtr rootPtr, int value);
TreeNodePtr search(TreeNodePtr rootPtr, int value);
void delete(TreeNodePtr rootPtr, int value);
int smallest(TreeNodePtr treePtr);
void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );

int main(int argc, char *argv[]) {
   int value;
   int i; /* counter to loop from 1-10 */
   int item;
   TreeNodePtr rootPtr = NULL; /* tree initially empty */

   srand(time(NULL));
   printf( "The numbers being placed in the tree are:\n" );

   /* insert random values between 0 and 14 in the tree */
   for ( i = 0; i <= 8; i++ ) {
      item = rand() % 15;
      printf( "%3d ", item);
      insertNode( &rootPtr, item );
   }
   printf("\n");
   postOrder(rootPtr);
   printf("\n");

   printf("Enter value to be deleted: ");
   scanf("%d", &value);
   delete(rootPtr, value);
   preOrder(rootPtr);
   printf("\n");

   return 0;
}

void delete(TreeNodePtr rootPtr, int value) {
   TreeNodePtr parentPtr = NULL;
   TreeNodePtr currPtr = NULL;
   TreeNodePtr tempPtr = NULL;
   int smallestVal;

   /* We must first find the parent node of the desired node */
   parentPtr=searchPar(rootPtr, value);

   /* Now find the actual node to be deleted. */
   currPtr=search(parentPtr, value);
   /* If node is a leaf */
   if (currPtr->leftPtr==NULL && currPtr->rightPtr==NULL) {
      printf("leaf\n");
      tempPtr=currPtr;

      /* We now must point the leftPtr or rightPtr of the parent node to NULL. */
      if (parentPtr!=NULL && parentPtr->leftPtr->data==currPtr->data) {
         parentPtr->leftPtr=NULL;
      } else if (parentPtr!=NULL && parentPtr->rightPtr->data==currPtr->data) {
         parentPtr->rightPtr=NULL;
      } else if (parentPtr!=NULL && parentPtr->data==currPtr->data) {
         parentPtr=NULL;
      }

      free(tempPtr);

   /* If node has one child */
   } else if (currPtr->leftPtr==NULL || currPtr->rightPtr==NULL ) {
      printf("one child\n");
      tempPtr=currPtr;

      /* If leftPtr of parent points to node. */
      if (parentPtr->leftPtr!=NULL && parentPtr->leftPtr->data==currPtr->data) {

         /* If the node has a child on its rightPtr */
         if (currPtr->leftPtr==NULL) {
            parentPtr->leftPtr=currPtr->rightPtr;

         /* If the node has a child on its leftPtr */
         } else {
            parentPtr->leftPtr=currPtr->leftPtr;
         }
      /* If rightPtr of parent points to node. */
      } else if (parentPtr->rightPtr!=NULL && parentPtr->rightPtr->data==currPtr->data) {

         /* If the node has a child on its rightPtr */
         if (currPtr->rightPtr==NULL) {
            parentPtr->rightPtr=currPtr->rightPtr;

         /* If the node has a child on its leftPtr */
         } else {
            parentPtr->rightPtr=currPtr->leftPtr;
         }
      }

      free(tempPtr);

   /* If node has two children */
   } else {
      printf("two children\n");
      smallestVal=smallest(currPtr);
      delete(currPtr, smallestVal);
      currPtr->data=smallestVal;
   }
}

void insertNode( TreeNodePtr *treePtr, int value ) {

   if ( *treePtr == NULL ) {
      *treePtr = malloc( sizeof( TreeNode ) );
      /* if memory was allocated then assign data */
      if ( *treePtr != NULL ) {
         ( *treePtr )->data = value;
         ( *treePtr )->leftPtr = NULL;
         ( *treePtr )->rightPtr = NULL;
      } else {
         printf( "%d not inserted. No memory available.\n", value );
      } /* end else */
   } else { /* tree is not empty */
      /* data to insert is less than data in current node */
      if ( value < ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->leftPtr ), value );
      } /* end if */
      /* data to insert is greater than data in current node */
      else if ( value > ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->rightPtr ), value );
      } else { /* duplicate data value ignored */
         printf( "dup" );
      } /* end else */
   } /* end else */

}
/* begin inorder traversal of tree */
void inOrder( TreeNodePtr treePtr ) {
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) {
      inOrder( treePtr->leftPtr );
      printf( "%3d", treePtr->data );
      inOrder( treePtr->rightPtr );
   } /* end if */
} /* end function inOrder */

/* begin postorder traversal of tree */
void postOrder( TreeNodePtr treePtr ) {
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) {
      postOrder( treePtr->leftPtr );
      postOrder( treePtr->rightPtr );
      printf( "%3d ", treePtr->data );
   } /* end if */

} /* end function postOrder */

/* begin preorder traversal of tree */
void preOrder( TreeNodePtr treePtr ) {
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) {
      printf( "%3d", treePtr->data );
      preOrder( treePtr->leftPtr );
      preOrder( treePtr->rightPtr );
   } /* end if */

} /* end function preOrder */

Thanks a lot.

Code:

  2
 / \
1   3

If you delete 2, the root node, then your delete function first has to deal with the possibility of removing the root node.

The second point is that having removed a node with LEFT and RIGHT branches, you need some way of rejoining the tree together, with either 1 or 3 as the new root.