• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 293
  • Last Modified:

How to delete a node recursively, given the key and other data?

hey guys,

i'm having trouble writing a function to delete a node from a tree recursively.
what i want is that once the node to be deleted, call this child, child->left, called left_child,  replaces child in the tree, left_child->right = child->right, called right_child, and so on.

so basically we are taking the left subtree and  moving it up to the deleted node.

i have the following as definition for the struct and the addNode:

struct diaryTag
{
  int date; // key
  int time; // key
  char *appointment;
  diaryType *left;
  diaryType *right;
} *root = NULL;


// inserts appointments with time
diaryType *addNode(diaryType *tmp, int date, int time, char *appoint)
{
  if(tmp == NULL)
    {
      // new node created
      if((tmp = (diaryType *)malloc(sizeof(struct diaryTag))) != NULL)
        {
        tmp->date = date;
        tmp->time = time;
        tmp->appointment = appoint;
        tmp->left = tmp->right = NULL;
      }
      else
      {
        printf("Not enough memory\n");
        exit (1);
      }
    }
  else if(date < tmp->date)
    {
      tmp->left = addNode(tmp->left, date, time, appoint);
    }
  else if(date == tmp->date)
    {
      if(time == -1)
      {
        tmp->left = addNode(tmp->left, date, time, appoint);
      }
      else if(time < tmp->time)
      {
        tmp->left = addNode(tmp->left, date, time, appoint);
      }
      else if(time == tmp->time)
      {
        if(strlen(appoint) <= strlen(tmp->appointment))
          {
            tmp->left = addNode(tmp->left, date, time, appoint);
          }
        else
          {
            tmp->right = addNode(tmp->right, date, time, appoint);
          }
      }
      else
      {
        tmp->right = addNode(tmp->right, date, time, appoint);
      }
    }
  else
    {
      tmp->right = addNode(tmp->right, date, time, appoint);
    }
  return tmp;
}

now, i read in a date, time (optional) and appointment from a file and can add it to the tree using the above function, but am unsure as to how to delete recursively

the delete function needs to always pick the left subtree to replace the deleted node.

can you help me write a function to do this, and if possible to keep track of the root node?

cheers
0
hitokiri_battousai
Asked:
hitokiri_battousai
  • 2
1 Solution
 
sunnycoderCommented:
>can you help me write a function to do this,
Since this could be homework, I will offer only hints ... Assume a tree like
                                           A
                                         /    \
                                        B      C
                                      /  \     /  \
                                     D   E   F   G

If you were to delete B, tree would look like
                                           A
                                         /    \
                                        D      C
                                         \     /  \
                                          E   F   G
Note that for this change, the left child pointer of A has changed ... this means that you will need to keep track of the parent node to be able to change the subtree. Assuming that you have addresses of A, B and D handy, all you need to do is
A->left = D
D->right = E
delete (B)

Now what if D had 2 children .. In that case you would not be able to set D->right without losing its original child!!!

Thus deletion in binary tree depends on how many children does the node have

Refer to these for the correct algorithm
http://www.cs.usask.ca/resources/tutorials/csconcepts/1998_6/bintree/2-5_1.html
http://www.cs.usask.ca/resources/tutorials/csconcepts/1998_6/bintree/2-5_1.html

>and if possible to keep track of the root node?
you can simply store it in a global or pass it along as parameter to every function ...

Cheers!
sunnycoder
0
 
smpoojaryCommented:
Explanation for the my sample code
a) consider tree as      
             10
             /    \
           5      15
         /  \    /   \
       2    8   13  18
      / \  / \
     1  3 6  9

After delete node with value 5 the tree should be  ((node->left != NULL) && (node->right != NULL))
              10
             /    \
           2      15
         /  \    /   \
       1    8   13  18
           / \
          6  9
         /
        3
b) consider the tree as
              10
             /    \
           5      15
         /       /   \
       2       13  18
      / \  
     1  3
After delete node with value 5 the tree should be  (node->right == NULL)
               10
             /    \
           2      15
         / \        /   \
       1   3     13  18

c) consider the tree as
               10
             /    \
           5      15
            \    /   \
            8   13  18
           / \
          6  9
After delete node with value 5 the tree should be (node->left == NULL)

               10
             /    \
           8      15
         /  \     /   \
       6    9   13  18
 
-Mahesh
0
 
smpoojaryCommented:
Sorry, but I have given some sample code
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now