int Nodi(tree T)
{ if ((!T) || (!T->left) || (!T->right)) return 0;
else return 1+Nodi(T->left)+Nodi(T->right);
}

Questa è la mia funzione di prima, e funziona ovunque, basta che gli passi il nodo da cui vuoi cominciare a contare. Nel caso nostro diventa una radice di un sottoalbero, e da lì conta. Non so se mi sono spiegato.