Counting nodes in binary search tree

Question

I need to create a recursive method that takes as a parameter the root node of a binary search tree. This recursive method will then return the int value of the total number of nodes that have one left descendant.

int Tree::leftPtrCount(int count) {
    return leftPtrCountHelper(rootPtr, count);
}
int Tree::leftPtrCountHelper(TreeNode *node, int count){
    if (node == NULL)
        return 0;
    if (node->leftPtr != NULL && node->rightPtr == NULL)
        count++;
    else
        return leftPtrCountHelper(node->leftPtr, count) + leftPtrCountHelper(node->rightPtr, count);
}

You don't return the counter in all cases, which leads to undefined behavior (and I guess that this is one of the problems you might be having). In fact, the counter is not needed at all. — Some programmer dude
Welcome on StackOverflow! This site has some etiquette that should be respected. Please read stackoverflow.com/questions/how-to-ask to help improving your question. — harper

Vlad from Moscow Vlad from Moscow · Accepted Answer · 2014-05-04T12:06:21

If I understand correctly the assignment then the function will look as

size_t Tree::leftPtrCountHelper( const TreeNode *node )
{
    if ( node == NULL ) return 0;
    return ( node->leftPtr != NULL && node->rightPtr == NULL ) +
             leftPtrCountHelper( node->leftPtr ) + 
             leftPtrCountHelper( node->rightPtr );
}

Counting nodes in binary search tree

1 Answers