# Count Number of Nodes in a Binary Tree

“** 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.

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

- Using Recursive Approach
- 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:

- Create an empty queue and push root node in it.
- Initialize count as 0.
- Do following while queue not empty:
- Increment count with 1.
- If left child of current node exists, push it into queue.
- If right child of current node exists, push it into queue.
- 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:**

**Introduction to Tree Data Structure****Binary Tree Traversals****Print All Leaf Nodes of a Binary Tree****Print Alternate Levels of Binary Tree****Maximum Width of Binary Tree****Level Order Tree Traversal****Left View of Binary Tree****Right View of Binary Tree****Compute Height of Binary Tree****Inorder Tree Traversal Using Stack****Preorder Tree Trasversal Using Stack****Postorder Tree Traversal Using Stack****Vertical Order Tree Traversal****Top View of Binary Tree****Bottom View of Binary Tree****Delete Complete Binary Tree****Check if two trees are mirror Trees of Each Other****Convert Binary Tree to its Mirror Tree****Check if Binary Tree is Symmetric or Not****Print All Root to Leaf Paths in a Binary Tree**