Write a program to count nodes in a tree

Approach:
Traverse all the nodes in a tree. You can do any traversal and just start counting. But there is a concept called tail recursion which is handy and very easily readable.
If you have a tree, if you know the number of nodes in the left and number of nodes in right +1, then, what you get is total number of nodes.

int count(node* root) {

    if(root == NULL)
        return 0;
    else if(root->left == NULL && root->right == NULL)
         return 1;
    else
         return count(root->left) + count(root->right) + 1;

}

One Thought on “Write a program to count nodes in a tree

  1. leaf node check is not required, below code will do:

    int count( struct node *root)
    {
    if(root == NULL)
    return 0;

    return count(root->left) + count(root->right) +1;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation