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