Thread: number of nodes in tree

The easiest way is to traverse the tree and count them. But if the tree is balanced you might want to try something like 2^n+1 - 1.

If the height of the tree is 2 then
2^n+1 - 1 = 2^3 - 1 = 7

The tree would look like this:

Code:

     *
  *     *
*  *   *  *

So it's good.

Prelude

Code:

int NodeCount( Node* pNode )
{
    if( pNode != NULL )
        return 1 + NodeCount( pNode->pLeftChild ) + NodeCount( pNode->pRightChild );
    else return 0;
}

Haven't tested it, looks correct though.