Get Number of Nodes in a Binary Tree

Question:

Given a binary tree, get the total number of nodes in it.

Example:

Consider the image given below:

Form the image above,

The total number of nodes are 7.

Solution:

This problem can be solved by recursive traversal.

Assume if you have only one node, and no left and right node.

Now, you will do
= 1 + get_num_of_nodes(left) + get_num_of_nodes(right)
= 1 + 0 + 0
= 1

Suppose,
if you have left and right children as shown below:

= 1 + get_node(left) + get_node(right)
= 1 + 1 + 1
= 3

We apply similar logic to all the nodes.

return 1 + get_num_of_nodes(left) + get_num_of_nodes(right);

We call “get_num_of_nodes” recursively for left and right nodes, and arrive at the solution.

Solution in C++

#include <iostream>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


int get_num_of_nodes(Node *root)  
{  
// Base case  
if (root == NULL)  
        return 0;  
 
return 1 + get_num_of_nodes(root->left) + 
           get_num_of_nodes(root->right);  
}  
  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    cout<<"Solution = " << get_num_of_nodes(root)<<endl; 

    return 0;  
}  

Output:

Solution = 7