Delete nodes that satisfy a property

80 Views Asked by At

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart from the necessary pointers LC and RS, an integer number. The function should traverse all the nodes of the ordered tree and for each node $u$ it should do the following:

If the rightmost child of $u$ in the ordered tree is a leaf, this child should be deleted.

So does this mean that we are given a binary tree like the following?

enter image description here

And then the corresponding ordered tree will be the following and we want to delete the nodes $C$ and $G$?

enter image description here

Or have I understood it wrong?

EDIT: I wrote the following algorithm:

Algorithm(node *A){
  node *p=A,*q=NULL;
  if (p==NULL) return;
  if (p->LC!=NULL){
      q=p->LC;
      if (q->RS!=NULL and q->RS->RS==NULL and q->RS->LC==NULL){
          q->RC=NULL;
      }
      if (q->LC!=NULL) Algorithm(q);
   }
   Algorirthm(q->RC);
}

Could you tell me if it is right?