Deleting a node in a Binary Search Tree - C

Question

I'm currently working on a school project where I have to write a few helper functions for Binary Search Trees. One of the functions removes a node from the tree. I'm trying to run some test cases but I can't seem to get them to work. I know the problem has something do with how I'm using pointers, but I'm not quite sure where I'm going wrong.

Here is the code:

int removeBST (struct TreeNode **rootRef, int data)
{
    struct TreeNode *current = *rootRef;
    struct TreeNode *temp = current;

    if (current == NULL)
        return 0;

    if (data < current->data) 
    {
        current->left = removeBST (&current->left, data);
    }

    if (data > current->data) 
    {
        current->right = removeBST (&current->right, data);
    }

    if (current->left == NULL || current->right == NULL)
        return 0;
    else 
    {
        if (current->left == NULL) {
            temp = current->right;
            current = temp;
            free (temp);
            return 1;
        } 
        else if (current->right == NULL) {
            temp = current->left;
            current = temp;
            free (temp);
            return 1;
        }
        temp = leftRoot (current->right);
        current->data = temp->data;
        current->right = removeBST (&current->right, temp->data);

    }

    return 1;
}

Note: I didn't include the leftRoot() function, but it's fairly simple and I know it does what it's supposed to (return the leftmost root in a subtree) Here is the part of the code my professor gave us that tests the remove function:

  for(i = -4; i < 25; i+=4)
  {
    n = removeBST(&bst, i);
    if(!n) printf("remove did not find %d\n", i);
  }

and in case it's necessary, here's the entire test code that creates the tree and inserts the data:

struct TreeNode* bst = NULL;
for(i = 0; i < 23; ++i)
  {
    n = (i*17+11) % 23;
    bst = insertBST(bst, n);
  }

  printf("filled BST: ");
  printTree(bst);
  printf("BST leaves: ");
  printLeaves(bst);
  printf("BST depth = %d\n", maxDepth(bst));
  printf("BST minimum value = %d\n", minValueBST(bst));
  printf("BST isBST = %d\n", isBST(bst));

  for(i = -4; i < 25; i+=4)
  {
    n = removeBST(&bst, i);
    if(!n) printf("remove did not find %d\n", i);  
  }

the entire output is:

filled BST: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 
BST leaves: 0 6 12 17 
BST depth = 8
BST minimum value = 0
BST isBST = 1
remove did not find -4
remove did not find 0
remove did not find 4
(this part repeats all the way up to 24)
BST after removes: 11

Since everything besides the '11' is no longer attached to tree, I'm fairly certain that something in my program is assigning pointers where they shouldn't be assigned and tree nodes are just getting lost in the void. Any ideas?

EDIT: One piece of information I forgot to provide, the deleted node's left-most child is supposed to replace the deleted node.

Answer 1

I'm not sure that I've found all of the issues in your code but here is one major one:

int removeBST (struct TreeNode **rootRef, int data)

Your function returns an int, corroborated by a number of return 1 or return 0 statements...

And yet you do this:

    if (data < current->data) 
    {
        current->left = removeBST (&current->left, data);
    }

    if (data > current->data) 
    {
        current->right = removeBST (&current->right, data);
    }

Since you're passing &current->left to the first argument the I can assume that it's type would be a pointer to a struct TreeNode **rootRef, which is struct TreeNode ***rootRef...

Which means that you're assigning addresses 0 and 1 to the left and right nodes? This seems very odd to me and is likely causing problems for you.

Note: this is not a solution but it is too big to fit into a comment.

Since you've opted for recursion let me see if I can help you fix this somewhat...

int removeBST (struct TreeNode **rootRef, int data)
{
    struct TreeNode *current = *rootRef;
    struct TreeNode *temp = current;

    if (current == NULL)
        return 0;

    if (data < current->data) 
    {
        // We don't want to modify things here, just let the next 
        // call take care of it and return what it returns.
        return removeBST(&current->left, data);
    }
    else if (data > current->data) 
    {
        // Same here.
        return removeBST(&current->right, data);
    }
    else 
    {
        if (current->left == NULL) {
            temp = current->right;
            // The rest of the stuff from here moved below.
            // Because I added the else, the return isn't needed 
            // here anymore either, since the one at the bottom 
            // will return 1 anyway.
        } 
        else if (current->right == NULL) {
            temp = current->left;
            // I did the same here.
        }
        else {
            temp = leftRoot (current->right);
            // This was on the outside but really it should be an else 
            // since it means less code...
            // Additionally, once you got the left root why did you decide
            // to remove it too? As far as I can see you only want to 
            // remove this one... If not, then you might have some work 
            // to do here...
        }

        *rootRef = temp; // current and rootRef are not the same. 
                         // You need to use rootRef here so that we 
                         // move the temp pointer to the current one 
                         // (replace it). Think carefully about where 
                         // the pointers are! Pointers also have addresses 
                         // and it matters what address you write to 
                         // where, use pen and paper and draw where things 
                         // point! 
        free (current);  // this means that we can't delete temp! so 
                         // since, we've just deleted the "current" 
                         // pointer we should discard it too...
    }

    return 1;
}

Draw a diagram for your pointers. I find diagrams like this or this help me most. It is not embarrassing and will help you understand what you're writing. It is important to visualize these things, particularly when you're just learning.

I've tried to fix the code up a little. I will admit that I didn't spend as much time as I possibly should have proof-reading it but it should be ok enough to give you an idea about the solution. Don't just copy/paste this, I don't guarantee it will work. But it should help you get onto the right path.