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 ..

2
Contributors
3
Replies
4
Views
11 Years
Discussion Span
Last Post by 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.

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 // node with R and L

}``````

correct ?? :-/

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 );
}
}``````
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.