Delete node from a C binary tree without messing it up

Question

I am a beginner working on a C binary tree library.I am wondering on how could I delete a node from a binary tree without messing up the entire thing.Here is how I create the tree:

the structure:

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

typedef struct Node TNode;
typedef struct Node *binary_tree;

Creation of the tree:

binary_tree NewBinaryTree(int value_root) {
    binary_tree newRoot = malloc(sizeof(TNode));
    if (newRoot) {
        newRoot->value = value_root;
        newRoot->left = NULL;
        newRoot->right = NULL;
    }
    return newRoot;
}

Adding elements to it:

void Insert(binary_tree *tree, int val) {
    if (*tree == NULL) {
        *tree = (binary_tree)malloc(sizeof(TNode));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
    } else {
        if (val < (*tree)->value) {
            Insert(&(*tree)->left, val);
        } else {
            Insert(&(*tree)->right, val);
        }
    }
}

my question is basically how I could for example delete a left node,and then "link" the other nodes(or leaves) that were linked to that left node so the tree doesnt have a NULL leaf? Ex: if leaf 4 had 2 children(left3 and right8),then delete leaf 4, it link children left3 and right8 to the upper node(above leaf4).Its hard to explain im trying to do my best.

thank you

There are plenty of reference material online, which tells you how deletion occurs in a binary search tree. Go through it first, or refer here. — mahesh Rao
If you have anymore questions, try to search for the answer. If you still don't find a solution, feel free to ask again or comment on stack overflow. Happy coding. — mahesh Rao

cru3lgenius cru3lgenius · Accepted Answer · 2016-12-12T07:50:36

The algorithm for deleting from a BST looks conceptually like this:

You search for the node using its key.
Once you have found the node you check if it has only one child.
- if it does, you remove the node and put on its place the child you just found.
- if it doesn't, you search for the node with the minimum value key in the right subtree. Once you find it, you replace the key of the node you want to delete with this minimum key and you delete the minimum node in the right subtree.

How this whole concept works and how should it look in C code you can read for example here. My suggestion would be to first see this diagram, which illustrates all the possible scenarios. Good luck!

Delete node from a C binary tree without messing it up

1 Answers