# Counting nodes in a binary tree recursively

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;
}


## 4 thoughts on “Counting nodes in a binary tree recursively”

1. Nasif Ali says:

It works

1. martin says:

Thank you, Nasif!

2. jokap says:

What is the complexity of this algorithm?

1. martin says:

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