The number of nodes in a binary tree is the number of nodes in the root’s left subtree, plus the number of nodes in its right subtree, plus one (for the root itself).

This lends itself to a simple recursive algorithm for counting the nodes in a binary tree.

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

It works

Thank you, Nasif!

What is the complexity of this algorithm?

It visits every node in the tree once, so it’s O(n).