How to remove node from binary tree?

Question

I modified an existing program that given the nodes, it will create a binary tree, calculate the Tree traversals, but I don't fully know how to remove a node. All I need is a simple function that would remove the node from the tree. Basically, the function should remove the node. For example:

          50                            50
       /     \         delete(20)      /   \
      30      70       --------->    30     70 
     /  \    /  \                     \    /  \ 
   20   40  60   80                   40  60   80






      50                             60
   /     \         delete(50)      /   \
  40      70       --------->    40    70 
         /  \                            \ 
        60   80                           80

My code:

#include<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
}

void main()
{
    node *root;
    node *tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);
    insert(&root, 0);
    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);
    /* Search node into tree */
    tmp = search(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }

    /* Deleting all nodes of tree */
    deltree(root);
}

Answer 1

I'm copying the comment as per OP's request.

I don't believe that asking for an entire function is okay. Therefore, here is an idea: first, find the node you want to remove. Then:

• If the node has no children, just remove it (free its memory and set the parent's pointer to NULL).

• If the node has a left child, find it's maximum, delete it from the subtree and replace that maximum instead of the given node.

• Else (if the node has the right child), remove the minimum from the right subtree and insert it in place of the node. You can do this without deleting the actual node (just the one from the subtree).