C Program to Count the Number of Nodes in Binary Tree

This is a C Program for counting the 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 <stdio.h>
```
```
#include <stdlib.h>
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node *left, *right;
```
```
};
```
```
struct node *createnode(int key)
```
```
{
```

    struct node *newnode = (struct node*)malloc(sizeof(struct node));

```
    newnode->info = key;
```
```
    newnode->left = NULL;
```
```
    newnode->right = NULL;
```
```
    return(newnode);
```
```
}
```
```
static int count = 0;
```
```
int countnodes(struct node *root)
```
```
{
```
```
    if(root != NULL)
```
```
    {
```
```
        countnodes(root->left);
```
```
        count++;
```
```
        countnodes(root->right);
```
```
    }
```
```
    return count;
```
```
}
```
```
/*
```
```
 * Main Function
```
```
 */
```
```
int main()
```
```
{
```
```
    /* Creating first Tree. */
```

    struct node *newnode = createnode(25);

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

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

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

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

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

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

    printf("Number of nodes in tree 1 = %d ",countnodes(newnode));

```
    printf("\n");
```
```
    count = 0;
```
```
 
```
```
    /* Creating second Tree. */
```
```
    struct node *node = createnode(1);
```
```
    node->right = createnode(2);
```
```
    node->right->right = createnode(3);
```

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

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

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

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

    printf("Number of nodes in tree 2 = %d ",countnodes(node));

```
    printf("\n");
```
```
    count = 0;
```
```
 
```
```
    /* Creating third Tree. */
```
```
    struct node *root = createnode(15);
```

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

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

    printf("Number of nodes in tree 3 = %d",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

If you wish to look at programming examples on all topics, go to C Programming Examples.

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

« Prev - C Program to Implement Circular Doubly Linked List

» Next - C Program to Print All Nodes of Nth Level in Single Line

Related Posts:

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

Recommended Articles: