Aug 222012

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.


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).

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


    /** Returns number of nodes in Binary Tree.
     * root: pointer to root node of tree  
    unsigned int countNodes(Node* root) 
        if (NULL == root) 
            return 0;
            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

 Leave a Reply

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=""> <s> <strike> <strong>