C++ Program to Count the Number of Nodes in Binary Tree

This is a C++ Program for counting number of nodes present in a tree using recursion.

Problem Description

Here in this problem we will be finding the total number of nodes present in a given tree using C++ Language.

Expected Input and Output

Case 1. Balanced Tree:When the weight is equal on both the sides of root.

                    25
                  /    \  
                 27     19   
                / \     / \ 
              17  91   13 55

Output: 7

Case 2. Right Skewed Tree:When the nodes at every level just have a right child.

                    1   
                     \
                      2    
                       \    
                        3 
                         \
                          4
                           \
                            5

Output: 5

advertisement
advertisement

Case 3. Tree having just one node

                    15

Output: 1

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Problem Solution

1. In order to count the number of nodes in a tree we just need to traverse the whole tree once. We can use any of the traversal techniques to count the number of nodes.
2. We have to take a count variable and initialize it with 0 and for each node which we traverse we just have to increase the value of count.

Program/Source Code

Here is source code of the C++ Program for counting the number of nodes present in a tree. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on windows 10. The program output is also shown below.

  1. /* C++ Program for counting the number of nodes in a Tree */
  2. #include<iostream>
  3. using namespace std;
  4. struct node *createnode(int key);
  5. int countnodes(struct node *root);
  6. static int count = 0;
  7. struct node
  8. {
  9.     int info;
  10.     struct node *left, *right;
  11. };
  12. class BST
  13. {
  14.     public:
  15.         struct node *createnode(int key)
  16.         {
  17.             struct node *newnode = new node;
  18.             newnode->info = key;
  19.             newnode->left = NULL;
  20.             newnode->right = NULL;
  21.             return(newnode);
  22.         }
  23.         int countnodes(struct node *root)
  24.         {
  25.             if(root != NULL)
  26.             {
  27.                 countnodes(root->left);
  28.                 count++;
  29.                 countnodes(root->right);
  30.             }
  31.             return count;
  32.         }
  33. };
  34. /*
  35.  * Main Function
  36.  */
  37. int main()
  38. {
  39.     BST t1,t2,t3;
  40.     /* Creating first Tree. */
  41.     struct node *newnode = t1.createnode(25);
  42.     newnode->left = t1.createnode(27);
  43.     newnode->right = t1.createnode(19);
  44.     newnode->left->left = t1.createnode(17);
  45.     newnode->left->right = t1.createnode(91);
  46.     newnode->right->left = t1.createnode(13);
  47.     newnode->right->right = t1.createnode(55);
  48.     /* Sample Tree 1:
  49.      *                25
  50.      *             /    \
  51.      *            27     19
  52.      *           / \     / \
  53.      *         17  91   13 55
  54.      */
  55.     cout<<"Number of nodes in tree 1 =  "<<t1.countnodes(newnode);
  56.     cout<<"\n";
  57.     count = 0;
  58.  
  59.     /* Creating second Tree. */
  60.     struct node *node = t2.createnode(1);
  61.     node->right = t2.createnode(2);
  62.     node->right->right = t2.createnode(3);
  63.     node->right->right->right = t2.createnode(4);
  64.     node->right->right->right->right = t2.createnode(5);
  65.     /* Sample Tree 2:   Right Skewed Tree (Unbalanced).
  66.      *               1
  67.      *                \
  68.      *                 2
  69.      *                  \
  70.      *                   3
  71.      *                    \
  72.      *                     4
  73.      *                      \
  74.      *                       5
  75.      */
  76.     cout<<"Number of nodes in tree 2 =  "<<t2.countnodes(node);
  77.     cout<<"\n";
  78.     count = 0;
  79.  
  80.     /* Creating third Tree. */
  81.     struct node *root = t3.createnode(15);
  82.     /* Sample Tree 3- Tree having just one root node.
  83.      *              15
  84.      */
  85.     cout<<"Number of nodes in tree 3 =  "<<t3.countnodes(root);
  86.     return 0;
  87. }
Program Explanation

Program contains two important functions.

advertisement

1. createnode(key);
This function helps to create a new node by allocating it a memory dynamically. It has just one parameter which is “key” which assigns value to the node thereby creating a fresh node having left and right child as “NULL”.

2. countnodes(struct node *root);
In this function we have traversed the left and right subtree and increased the count variable which counts the total number of nodes present in the left and the right subtree. The traversal technique which we have used here is inorder traversal of a tree, by first passing root->left then instead of printing the root->data as a next step of inorder traversal we increase the count variable and then we have passed the root->right to traverse the right subtree and count the total number of nodes present in the right subtree.

Runtime Test Cases
Number of nodes in tree 1 = 7
Number of nodes in tree 2 = 5
Number of nodes in tree 3 = 1

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.