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.

Output: 5

Case 3. Tree having just one node

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.

/* C++ Program for counting the number of nodes in a Tree */

```
#include<iostream>
```
```
using namespace std;
```
```
struct node *createnode(int key);
```
```
int countnodes(struct node *root);
```
```
static int count = 0;
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *left, *right;
```
```
};
```
```
class BST
```
```
{
```
```
    public:
```

        struct node *createnode(int key)

```
        {
```

            struct node *newnode = new node;

```
            newnode->info = key;
```
```
            newnode->left = NULL;
```
```
            newnode->right = NULL;
```
```
            return(newnode);
```
```
        }
```

        int countnodes(struct node *root)

```
        {
```
```
            if(root != NULL)
```
```
            {
```
```
                countnodes(root->left);
```
```
                count++;
```

                countnodes(root->right);

```
            }
```
```
            return count;
```
```
        }
```
```
};
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main()
```
```
{
```
```
    BST t1,t2,t3;
```
```
    /* Creating first Tree. */
```

    struct node *newnode = t1.createnode(25);

```
    newnode->left = t1.createnode(27);
```
```
    newnode->right = t1.createnode(19);
```

    newnode->left->left = t1.createnode(17);

    newnode->left->right = t1.createnode(91);

    newnode->right->left = t1.createnode(13);

    newnode->right->right = t1.createnode(55);

```
    /* Sample Tree 1:
```
```
     *                25
```
```
     *             /    \
```
```
     *            27     19
```
```
     *           / \     / \
```
```
     *         17  91   13 55
```
```
     */
```

    cout<<"Number of nodes in tree 1 =  "<<t1.countnodes(newnode);

```
    cout<<"\n";
```
```
    count = 0;
```
```
 
```
```
    /* Creating second Tree. */
```

    struct node *node = t2.createnode(1);

```
    node->right = t2.createnode(2);
```

    node->right->right = t2.createnode(3);

    node->right->right->right = t2.createnode(4);

    node->right->right->right->right = t2.createnode(5);

    /* Sample Tree 2:   Right Skewed Tree (Unbalanced).

```
     *               1
```
```
     *                \
```
```
     *                 2
```
```
     *                  \
```
```
     *                   3
```
```
     *                    \
```
```
     *                     4
```
```
     *                      \
```
```
     *                       5
```
```
     */
```

    cout<<"Number of nodes in tree 2 =  "<<t2.countnodes(node);

```
    cout<<"\n";
```
```
    count = 0;
```
```
 
```
```
    /* Creating third Tree. */
```

    struct node *root = t3.createnode(15);

    /* Sample Tree 3- Tree having just one root node.

```
     *              15
```
```
     */
```

    cout<<"Number of nodes in tree 3 =  "<<t3.countnodes(root);

```
    return 0;
```
```
}
```

Program Explanation

Program contains two important functions.

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.

« Prev - C++ Program to Count Leaf Nodes in a Binary Search Tree

» Next - C++ Program to Create Expression Tree from Postfix Expression

Related Posts:

Check Computer Science Books
Apply for Computer Science Internship
Practice Computer Science MCQs
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books

Recommended Articles: