This is the counterpart of counting leaves in a binary tree recursively. If we are an internal node, we count 1 for ourselves, then recurse into the left and right subtrees and sum the count of internal nodes in them.

unsigned int binarytree_count_internal_nodes_recursive(const btnode *root)
{
unsigned int count = 0;
if (root->left != NULL || root->right != NULL) {
count = 1;
if (root->left != NULL) {
count += binarytree_count_internal_nodes_recursive(root->left);
}
if (root->right != NULL) {
count += binarytree_count_internal_nodes_recursive(root->right);
}
}
return count;
}
unsigned int binarytree_count_internal_nodes(const binarytree *tree)
{
unsigned int count = 0;
if (tree->root != NULL) {
count = binarytree_count_internal_nodes_recursive(tree->root);
}
return count;
}