Delete Binary Tree Node

Hello,

After about a week of trying to figure out how to write a function that would take into consideration all aspects of deleting a node from a binary tree... I succeeded. After writing the function, I looked at it, and said to myself, "There has to be a way to make this easier to write and easier to read."

Since I am teaching myself, I wanted the communities input as to how I could have approached this differently, how I can reduce my code, if necessary (I have a feeling I could have used recursion), comments, critisism, etc. Below is the code:

Code:

---

void delete_node(BTREE *node, int value)
{
        BTREE *current = NULL, *del_node = NULL, *child = NULL;
        BTREE *parent = NULL, *x = NULL;
        current = node;               
       
        while (current != NULL) {               
                if (value == current->num) {
                del_node = current;
                //case 1: node is a leaf (no descendants)
                        if ((del_node->left == NULL) && (del_node->right == NULL)) {
                                //if the node to delete is to the left of root
                                if (parent->left == del_node) {
                                        parent->left = NULL;
                                        free(del_node);
                                        printf("Node deleted\n");
                                        break;
                                }
                                //if the node to delete is to the right of root
                                else if (parent->right == del_node) {
                                        parent->right = NULL;
                                        free(del_node);
                                        printf("Node deleted\n");
                                        break;
                                }
                        }
                //case 2: node has one child
                        else if ((del_node->left == NULL) || (del_node->right == NULL)) {
                                printf("Node has one child\n");
                                //if the node to delete is to the left of root
                                if (parent->left == del_node) {
                                        if (del_node->left != NULL) {
                                                child = del_node->left;
                                                parent->left = child;
                                                free(del_node);
                                                break;
                                        }
                                        else if (del_node->right != NULL) {
                                                child = del_node->right;
                                                parent->left = child;
                                                free(del_node);
                                                break;
                                        }
                                }
                                //if the node to delete is to the right of root
                                else if (parent->right == del_node) {
                                        if (del_node->left != NULL) {
                                                child = del_node->left;
                                                parent->right = child;
                                                free(del_node);
                                                break;
                                        }
                                        else if (del_node->right != NULL) {
                                                child = del_node->right;
                                                parent->right = child;
                                                free(del_node);
                                                break;
                                        }
                                }                                               
                        }
                //case 3: node has two children       
                        else if ((del_node->left != NULL) && (del_node->right != NULL)) {
                                printf("Node has two children\n");
                                x = del_node;
                                //if the node to delete is root
                                if (parent == NULL) {
                                        child = del_node->right;
                                        if (child->left == NULL) {
                                                child->left = del_node->left;
                                                free(del_node);
                                                break;
                                        }
                                        else {
                                                while (child->left != NULL) {
                                                                parent = child;
                                                                child = parent->left;
                                                }
                                                x->num = child->num;
                                                parent->left = child->right;
                                                del_node = child;
                                                free(del_node);
                                                break;
                                        }                                               
                                }
                                //if the node to delete is to the left of root
                                else if (parent->left == del_node) {
                                        child = del_node->right;
                                        if (child->left == NULL) {
                                                parent->left = child;
                                                child->left = del_node->left;
                                                free(del_node);
                                                break;
                                        }
                                        else {
                                                while (child->left != NULL) {
                                                                parent = child;
                                                                child = parent->left;
                                                }
                                                x->num = child->num;
                                                parent->left = child->right;
                                                del_node = child;
                                                free(del_node);
                                                break;
                                        }
                                }
                                //if the node to delete is to the right of root
                                else if (parent->right == del_node) {
                                        child = del_node->right;
                                        if (child->left == NULL) {
                                                parent->right = child;
                                                child->left = del_node->left;
                                                free(del_node);
                                                break;
                                        }
                                        else {
                                                while (child->left != NULL) {
                                                                parent = child;
                                                                child = parent->left;
                                                }
                                                x->num = child->num;
                                                parent->left = child->right;
                                                del_node = child;
                                                free(del_node);
                                                break;
                                        }
                                }
                        }               
                }
                //if value is less than the node's value - go left
                else if (value < current->num) {
                        parent = current;
                        current = current->left;
                }
                //if value is greater than the node's value - go right
                else {
                        parent = current;
                        current = current->right;
                }
        }               
}

---

Thank you for taking the time to read this thread and provide any comments.

Considering everything is true in the beginning, parent isn't pointed to anything, but you use parent->left. Doesn't this crash your program?

Reducing your code = using more functions

When you have the same code, but just change "left" with "right", you can use a function and have a pointer as a parameter. Then you just pass either left or right. So it would be something like

Code:

---

if (parent->right == del_note)
  del_single_child(del_note);
else
  del_single_child(del_note);

---

This also help people understand more easily your code. Reading "del_single_child" they have all the information they need. If they want more, they can read the actual code of the function (rather sub-function).

Thanks for the reply C_ntua,

After I posted the code, I realized there were 2 cases that would occur that I hadn't accounted for:

If the root node only had one child and if the root node was the only node in the tree.

When I performed a test, the program did crash, because parent was initialized to NULL. Once I took those cases into account, I changed the code a little bit and it all seems to be working ok now.

I see what your saying about reducing the code by using more functions, but I think I would have to implement more than one function in the case of:

Code:

---

if (parent->right == del_note)
  del_single_child(del_note);
else
  del_single_child(del_note);

---

I think something like:

Code:

---

if (parent->right == del_note)
  del_single_child_right(del_note);
else
  del_single_child_left(del_note);

---

would work better only because I have to reinitialize parent->left or parent->right differently depending on if I go left or right.

I remember reading somewhere on the internet that if you write the function iteratively, the code's performance is better than if you write the function recursively. Something to do with each recursive functions' call being pushed and popped off the stack. Is it better to have more functions that use an iterative technique to reduce my code or better to use recursion?

By far the greatest simplification you can make to that code would be to use recursion and have the code pass a pointer-to-a-pointer to the node rather then just a single-pointer, so that none of the code has to know whether the node being deleted comes from a left or a right of a node or from the root. Instead it just NULLs whatever was passed in.

This is a minimal example to demonstrate that concept, and is meant to contain memory leaks etc, but the finished code needn't be more than about two to three times this size.

Code:

---

void delete_node(BTREE **node, int value)
{
    if (*node == NULL)
        return;
    else if ((*node)->num < value)
        delete_node(&(*node)->left, value);
    else if ((*node)->num > value)
        delete_node(&(*node)->right, value);
    else
    {

        // TODO: deal with our children here

        free *node;
        *node = NULL;
    }
}

---

iMalc,

Thanks for the reply. When I started to think about how I could implement recursion, I came to a problem. In my original code, I knew how to handle each case because I knew which node was the parent of the node I was going to delete. When I think about using recursion, for example, if I had a sample tree:

Code:

---

      90
    /    \
    /      \
  X      140
        /    \
        /      \
      125        175
    /    \    /    \
  /      \  /      \
  X        X X        X

---

and I wanted to delete the number 140, and I used recursion to move from 90 to 140, how would I keep account of the pointer that got me there? I know once I found the node I could just delete it, but how would the parent->right pointer get updated with the new node it should point to?