Approach:
Traverse all the nodes in a tree. You can do any traversal and just start counting. But there is a concept called tail recursion which is handy and very easily readable.
If you have a tree, if you know the number of nodes in the left and number of nodes in right +1, then, what you get is total number of nodes.
int count(node* root) { if(root == NULL) return 0; else if(root->left == NULL && root->right == NULL) return 1; else return count(root->left) + count(root->right) + 1; }
leaf node check is not required, below code will do:
int count( struct node *root)
{
if(root == NULL)
return 0;
return count(root->left) + count(root->right) +1;
}