CODEWITHSUNDEEP
ctreebinary-tree
Mimic01
Mimic01

Reputation: 107

Delete function in Binary Tree in C

I'm writing the basic functions for binary tree and everything seems to compile and run, but when i try to use my delete function it doesn't do anything.

After executing i get the same sequence of numbers, so i'm trying to figure out what's wrong with the Delete function, is it logically correct?

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

typedef struct treeNode
{
   int data;
   struct treeNode *left;
   struct treeNode *right;
}treeNode;

treeNode *Insert(treeNode *node, int data)
{
    if(node == NULL)
    {
    treeNode *temp;
    temp = malloc(sizeof(treeNode));
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
    }

    if(data > (node->data))
    {
    node->right = Insert(node->right, data);
    }

    else if(data < (node->data))
    {
    node->left = Insert(node->left, data);
    }
return node;
}

treeNode *Delete(treeNode *node, int data)
{
   if(node == NULL)
   {
    printf("element not found\n");
   }

   else if(data < node->data)
   {
    node->left = Delete(node->left, data);
   }

  else if(data > node->data)
  {
    node->right = Delete(node->right, data);
  }
return node;
}

treeNode *Find(treeNode *node, int data)
{
   if(node == NULL)
   {
    return NULL;
   }

   if(data > node->data)
   {
    return Find(node->right, data);
   }

   else if(data < node->data)
   {
    return Find(node->left, data);
   }

   else
   {
    return node;
   }
}

void Print(treeNode *node)
{
   if(node == NULL)
   {
    return;
   }
   Print(node->left);
   printf("%d", node->data);
   Print(node->right);
}

int main()
{
  treeNode *root = NULL;

  root = Insert(root, 5);
  root = Insert(root, 8);
  root = Insert(root, 6);
  root = Insert(root, 4);
  root = Insert(root, 3);
  root = Insert(root, 9);
  root = Insert(root, 10);
  root = Insert(root, 19);

  Print(root);
  printf("\n");

  root = Delete(root, 5);
  root = Delete(root, 8);

  Print(root);
  printf("\n");

  treeNode *temp;

  temp = Find(root, 8);
   if(temp == NULL)
   {
    printf("Element 8 not found\n");
   }
   else
   {
    printf("Element 8 found\n");
   }

  temp = Find(root, 5);
  if(temp == NULL)
  {
    printf("element 5 not found\n");
  }
  else
  {
    printf("element 5 found\n");
  }
}

Upvotes: 0

Views: 4574

Answers (1)

Mimic01
Mimic01

Reputation: 107

Basically i was only replacing the node with itself, but this can be solved by replacing the deleted node with the minimum element in the right subtree or the maximum element in the left subtree.

The function that works:

treeNode * Delete(treeNode *node, int data)
{
    treeNode *temp;
    if(node==NULL)
      {
        printf("Element Not Found");
      }
    else if(data < node->data)
      {
        node->left = Delete(node->left, data);
      }
    else if(data > node->data)
      {
        node->right = Delete(node->right, data);
      }
    else
      {
    /* Now We can delete this node and replace with either minimum element 
               in the right sub tree or maximum element in the left subtree*/
        if(node->right && node->left)
          {
        /* Here we will replace with minimum element in the right sub tree */
            temp = FindMin(node->right);
            node -> data = temp->data; 
    /* As we replaced it with some other node, we have to delete that node */
            node -> right = Delete(node->right,temp->data);
          }
        else
           {
        /* If there is only one or zero children then we can directly 
                       remove it from the tree and connect its parent to its child */
            temp = node;
             if(node->left == NULL)
                    node = node->right;
             else if(node->right == NULL)
                    node = node->left;
            free(temp); /* temp is longer required */ 
            }
    }
    return node;

}

Upvotes: 1

Related Questions