MHB Deleting Leaf Nodes from an Ordered Binary Tree

[evinda]

Hi! (Nerd)

Given a tree, I want to write an algorithm, that deletes from each node, from the corresponding ordered binary tree, the rightmost child, that is a leaf.

That's what I have tried:

Algorithm(NODE *P){
   if (P==NULL) return error;
   if (P->RC!=NULL) P=P->RC;
   if (P->LC!=NULL) Algorithm(P->LC);
   if (P->RC==NULL) P->LC->RC=NULL;
   Algorithm(P->RC)

Could you tell me if it is right?

 

[evinda]

I think that there are some mistakes.. But, is it entirely wrong? (Thinking)

 

[I like Serena]

Given a tree, I want to write an algorithm, that deletes from each node, from the corresponding ordered binary tree, the rightmost child, that is a leaf.

Algorithm(NODE *P){
   if (P==NULL) return error;
   if (P->RC!=NULL) P=P->RC;
   if (P->LC!=NULL) Algorithm(P->LC);
   if (P->RC==NULL) P->LC->RC=NULL;
   Algorithm(P->RC)

I think that there are some mistakes.. But, is it entirely wrong? (Thinking)

Hi! (Happy)

You have the set up for a recursive algorithm, which includes a check for the final condition, and recursive calls.
Good! (Smile)

   if (P==NULL) return error;

What is the reason that you think this results in an error? (Wondering)

   if (P->RC!=NULL) P=P->RC;

This seems to break the set up of the recursive function call.
As a result the left sub tree will not be visited any more.
Should it be like that? (Wondering)

   if (P->LC!=NULL) Algorithm(P->LC);

The check for a NULL pointer seems redundant, since we'll check that in the function anyway. (Nerd)

   if (P->RC==NULL) P->LC->RC=NULL;

What should this do?

If there is no child on the right side, set the grand child on the left side to NULL?
That doesn't seem to make sense. (Worried)

Btw, I think deleting a node should involve calling [m]free()[/m]. (Nerd)