Binary Search Tree in C: remove node function

Question

I'm putting together functions for a binary search tree and ran into a wall. I'm working on each situation that might be encountered when a node holding a specified value needs to be removed from the tree. I'm uncertain how to handle freeing the node if it does not have a left and right child. The function must return a node. Do I back up, examine each left and right child, and remove the value while it's in a child? But then if the value is in the root, wouldn't I have a similar problem with how to remove it? Just by way of explanation, the program uses a void pointer then casts the TYPE val in a separate function compare() which evaluates both values and returns -1 for <, 0 for ==, and 1 for >.

struct Node *_removeNode(struct Node *cur, TYPE val)
{
    if (compare(cur->val, val) == 0) { //if val == cur->val
        if (cur->right != NULL && cur->left != NULL) { //if cur has right and left
            cur = _leftMost(cur->right);
            free(_leftMost(cur->right));
        }
        else if (cur->right == NULL && cur->left != NULL) {  //if cur has left
            cur = cur->left;
            free(cur->left);
        }
        else if (cur->right != NULL && cur->left == NULL){ //if cur has right
            cur = cur->right;
            free(cur->right);
        }
        else if (cur->right == NULL && cur->left == NULL){ //if cur has no child
                //free cur if cur = val

        }
    }
    else if (compare(cur->val, val) == -1) {
        cur->right = _removeNode(cur->right, val);
    }
    else if (compare(cur->val, val) == 1) {
        cur->left = _removeNode(cur->left, val);
    }

    return cur;
}

Answer 1

If the node has neither child then it can simply be deleted. In order to make your recursion in the other cases work, you should return NULL from _removeNode. In all cases, cur should be deleted (freed) as it is no longer needed. In each case, you need to return the replacement subtree. The complication occurs in the first case where the left most descendent of the right child is pulled up. After pulling it up, you need to remove it from the right sub-tree (note that it may be the right sub-tree).

I wrote all of the below off the top of my head so be prepared for a few errors/a bit of debugging. Also, _leftMost and _removeLeftMost can be merged with a bit of work.

The block in question should look something like:

    Node *replacement;
    if (cur->right != NULL && cur->left != NULL) { //if cur has right and left    
        replacement = _leftMost(cur->right);
        replacement->right = _removeLeftMost(cur->right,replacement);
        replacement->left = cur->left;
    }
    else if (cur->right == NULL && cur->left != NULL) {  //if cur has left
        replacement = cur->left;
    }
    else if (cur->right != NULL && cur->left == NULL){ //if cur has right
        replacement = cur->right;
    }
    else if (cur->right == NULL && cur->left == NULL){ //if cur has no child
        replacement = NULL;
    }
    free(cur);
    cur = replacement;

The function _removeLeftMost walks down the left child pointers until it sees the node to be replaced and then replaces it with the right child of that node. Something like:

Node *_removeLeftMost(node, remove) {
    if (node == remove) {
       return node->right; // Note that remove->left should be null
    }
    else {
       node->left = _removeLeftMost(node->left,remove);
       return node;
    }
}

Also, the main call is something like

root = _removeNode(root, val);

So that handles your concern when the node is the root.