Tag Archives: Recursion

Counting nodes in a binary tree recursively

4 Comments

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

Related