Count Number of Nodes in a Binary Tree

by · January 21, 2021

“Count Number of Nodes in a Binary Tree” is again a very basic problem of tree data structure. Here, we are given a tree and our task is to count the number of nodes in a tree.

Count Number of Nodes in a Binary Tree
Total Number of Nodes in a Binary Tree

There can be multiple methods to count the number of nodes in a binary tree. Some of them are:

  1. Using Recursive Approach
  2. Using Queue Data Structure

METHOD 1: Using Recursive Approach

This is a brute-force approach to count number of nodes in a binary tree. The steps required to count number of nodes in a binary tree are as follows:

  • Initialize “count” variable as 1.
  • If root is NULL, return 0.
  • Else, 

count = count + countNodes(root -> left) and 

count = count + countNodes(root -> right

  • Then, return count.

C++ Program to count number of nodes in a binary tree is as follows:

/* C++ Program to count number of nodes in a Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to count number of nodes in a Binary Tree */
int countNodes(Node *root)
{
    int count = 1;  /* Node itself should be counted */
    
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        count = count + countNodes(root -> left);
        count = count + countNodes(root -> right);
        return count;
    }
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to Count Total Number of Nodes in a Binary Tree */
    cout<<"The Total Number of Nodes in a Binary Tree are "<<countNodes(root);
}

OUTPUT:

The Total Number of Nodes in a Binary Tree are 9

METHOD 2: Using Queue Data Structure

Here, the idea is to use level-order traversal to count number of nodes in a binary tree.

The steps required to count number of nodes in a binary tree are as follows:

  1. Create an empty queue and push root node in it.
  2. Initialize count as 0.
  3. Do following while queue not empty:
  4. Increment count with 1.
  5. If left child of current node exists, push it into queue.
  6. If right child of current node exists, push it into queue.
  7. Pop out the current node from queue.

C++ Program to count number of nodes in a binary tree are as follows:

/* C++ Program to count number of nodes in a Binary Tree */
#include<bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int data;
    struct Node *left;
    struct Node *right;
    Node(int ele)
    {
        data = ele;
        left = NULL;
        right = NULL;
    }
} Node;

/* Function to count number of nodes in a Binary Tree */
int countNodes(Node *root)
{
    /* Basic Test Case Scenerio */
    if(root == NULL)
    return 0;
    
    /* Create Queue and push root node in it */
    queue <Node *> qu;
    qu.push(root);
    
    int count = 0;
    
    /* Apply Level-Order Traversal  */
    while(!qu.empty())
    {
        count ++;
        
        if(qu.front() -> left)
        qu.push(qu.front() -> left);
        
        if(qu.front() -> right)
        qu.push(qu.front() -> right);
        
        qu.pop();
    }
    return count;
}

int main()
{
    /* Creating a Binary tree and inserting some nodes in it */
    Node *root = NULL;
    
    root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node (7);
    root -> left -> right -> left = new Node(8);
    root -> right -> left -> right = new Node(9);
    
    /* Calling function to Count Total Number of Nodes in a Binary Tree */
    cout<<"The Total Number of Nodes in a Binary Tree are "<<countNodes(root);
}

OUTPUT:

The Total Number of Nodes in a Binary Tree are 9

Related Posts:

  1. Introduction to Tree Data Structure
  2. Binary Tree Traversals
  3. Print All Leaf Nodes of a Binary Tree
  4. Print Alternate Levels of Binary Tree
  5. Maximum Width of Binary Tree
  6. Level Order Tree Traversal
  7. Left View of Binary Tree
  8. Right View of Binary Tree
  9. Compute Height of Binary Tree
  10. Inorder Tree Traversal Using Stack
  11. Preorder Tree Trasversal Using Stack
  12. Postorder Tree Traversal Using Stack
  13. Vertical Order Tree Traversal
  14. Top View of Binary Tree
  15. Bottom View of Binary Tree
  16. Delete Complete Binary Tree
  17. Check if two trees are mirror Trees of Each Other
  18. Convert Binary Tree to its Mirror Tree
  19. Check if Binary Tree is Symmetric or Not
  20. Print All Root to Leaf Paths in a Binary Tree

You may also like...