N. Ali. N. Ali. - 3 years ago 82
C Question

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;
}

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download