Delete nodes with a specific property

[evinda]

Hi! (Mmm)

I want to write a function that takes as argument a pointer [m]A[/m] 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 [m]LC[/m] and [m]RS[/m], an integer [m]number[/m].
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.

That's what I have tried:

    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?

 

[Future Bruno]

No, your algorithm is not correct. The problem with your algorithm is that it only checks the rightmost child of the root node, but it does not check any of the other nodes in the tree. To solve this problem, you need to traverse the entire tree and check each node for a rightmost leaf. Here is a better solution: void deleteRightmostLeaf(node *A){ if (A==NULL) return; //Check if current node has a rightmost leaf if (A->RS != NULL && A->RS->LC == NULL && A->RS->RC == NULL) A->RS = NULL; //Traverse through left and right subtrees deleteRightmostLeaf(A->LC); deleteRightmostLeaf(A->RC); }