Introduction
The recursive structure of a binary tree makes it easy to count nodes recursively. There are 3 things we can count:
- The total number of nodes
- The number of leaf nodes
- The number of internal nodes
Counting all nodes
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; }
Counting leaf nodes
This is similar, except that we only return 1 if we are a leaf node. Otherwise, we recurse into the left and right subtrees and return the sum of the leaves in them.
unsigned int binarytree_count_leaves_recursive(const btnode *root) { unsigned int count = 0; if (root->left == NULL && root->right == NULL) { count = 1; } else { if (root->left != NULL) { count += binarytree_count_leaves_recursive(root->left); } if (root->right != NULL) { count += binarytree_count_leaves_recursive(root->right); } } return count; } unsigned int binarytree_count_leaves(const binarytree *tree) { unsigned int count = 0; if (tree->root != NULL) { count = binarytree_count_leaves_recursive(tree->root); } return count; }
Counting internal nodes
This is the counterpart of counting leaves. 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; }