CODEWITHSUNDEEP
cbinary-search-tree
N. Ali.
N. Ali.

Reputation: 37

Having trouble with a binary search tree remove function

I'm attempting to remove a given value from a binary search tree. The function returns 1 if the given value was present, and 0 if it wasn't. I don't think I'm returning values properly. The proper values seem to be removed, but I'm printing a removal message when I shouldn't be, indicating that the function is returning 0 when it shouldn't be. Can anybody help me spot my error? Thanks.

/*Remove data from BST pointed to by rootRef, changing root if necessary.
* For simplicity's sake, always choose node's in-order
* successor in the two-child case.
* Memory for removed node should be freed.
* Return 1 if data was present, 0 if not found. */

int removeBST(struct TreeNode** rootRef, int data)
{  
  struct TreeNode* heir;
  struct TreeNode* prev;

  if(*rootRef == NULL)
  {
    return 0;
  }

  if(data < (*rootRef)->data)
  {
    removeBST(&(*rootRef)->left, data);
  }
  else if(data > (*rootRef)->data)
  {
    removeBST(&(*rootRef)->right, data);
  }
  else
  {
    struct TreeNode* temp;

    if((*rootRef)->right == NULL)
    {
      temp = *rootRef;
      *rootRef = (*rootRef)->left;
      free(temp);
    }
    else if((*rootRef)->left == NULL)
    {
      temp = *rootRef;
      *rootRef = (*rootRef)->right; 
      free(temp);
    }
    else
    {
      heir = (*rootRef)->left;
      prev = *rootRef;

      while(heir->right != NULL)
      {
        prev = heir;
        heir = heir->right;
      } 

      (*rootRef)->data = heir->data;

      if(prev != *rootRef)
      {
        prev->right = heir->left;
      }
      else
      {
         prev->left = heir->left;
      }
      free(heir);
   }
   return 1;
  }
  return 0;
}

Upvotes: 1

Views: 101

Answers (2)

Tom Karzes
Tom Karzes

Reputation: 24052

When it calls itself recursively, it needs to return the value from the recursive call. So change:

removeBST(&(*rootRef)->left, data);

to:

return removeBST(&(*rootRef)->left, data);

and similarly for the right-hand case. Without this, it is just falling through and returning 0 for these cases.

Upvotes: 4

Boiethios
Boiethios

Reputation: 42759

Replace

if(data < (*rootRef)->data)
{
  removeBST(&(*rootRef)->left, data);
}
else if(data > (*rootRef)->data)
{
  removeBST(&(*rootRef)->right, data);
}

with

if(data < (*rootRef)->data)
{
  return removeBST(&(*rootRef)->left, data);
}
else if(data > (*rootRef)->data)
{
  return removeBST(&(*rootRef)->right, data);
}

When you call the function, you did not use the return value.

Upvotes: 2

Related Questions