Solved

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

Posted on 2005-05-06
283 Views
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
Question by:hitokiri_battousai

LVL 45

Expert Comment

>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

>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

LVL 4

Accepted Solution

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

LVL 4

Expert Comment

Sorry, but I have given some sample code
0

## Featured Post

### Suggested Solutions

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.