tell me how to solve "counting Problem" in a BTree ?

[Zay]

Hello;

i have this Question and need your help, i do not know how to solve it;

Problem:
Write a member function called countNodeWithNoRchild that will return the number of nodes in a BT(binary Tree) does not have a right child. (Hint: a leaf node also does not have a right child)

i try to do it but the ways i followed are wrong , because there are some missing node not visited yet ..

[Narue]

Have you written a function that tells you the height of a binary search tree? If you have, you can use the same principles to solve this problem. If you haven't, you need to do a complete traversal of the tree (recursive is easiest) and for each node, return the count of the nodes below it that have no right child. The hint in your problem gives you the base case for recursion.

[Zay]

see my code , i do it using recursion

int count(nodeType<T> *p)
{ if (p==NULL)  // when reach the end or this is an empty tree
return 0;
 
else if (p->rlink==NULL && p->llink!=NULL)
return (1+count(p->llink));
 
else if(p->rlink==NULL&&p->llink==NULL)//leaf node no R & no L
return(1+count(p->llink));
 
else // node with R and L
return (1+count(p->rlink), count(p->llink));
 
}

correct ?? :-/

[Narue]

Basically what you're doing is a typical node count, but you only increment the count when p->rlink is null. Something along these lines:

int count ( nodeType<T> *p )
{
  if ( p == NULL )
    return 0;
  else {
    int left = count ( p->llink );
    int right = count ( p->rlink );

    return right + left + ( p->rlink == NULL );
  }
}