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”

Comments are closed.