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.

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