Number of nodes in a binary tree

Write a function which will return the total number of nodes in a Binary tree. For example, the Binary tree on the right has 7 nodes.

Solution:

Binary Tree problems can be easily solved using recursion.

To calculate the total number of nodes we can traverse the entire tree and increment the counter for each Node. Tree traversals are already discussed here and here. Just add a static variable count in the traversal and return it.

The below code does exactly that (just that we are not using a static variable, rather we are returning the size).

Algorithm:

If tree is empty
    return 0
Else
    return 1 + Number_of_Nodes_In_Left_subtree + Number_of_Nodes_In_Right_subtree

Code:

    /** Returns number of nodes in Binary Tree.
     *
     * root: pointer to root node of tree
     */
    unsigned int countNodes(Node* root)
    {
        if (NULL == root)
            return 0;
        else
            return ( 1 + countNodes(root->lptr) + countNodes(root->rptr) );
    }

The structure of Node of the Binary Tree is

    struct Node
    {
        int data;
        Node* lptr; // ptr to Left subtree
        Node* rptr; // ptr to Right subtree
    };