C Program to Count Non Leaf Nodes in a Tree

This is a C Program to calculate number of non leaf nodes in a tree.

Problem Description

We are given a tree, and we have to write a C program to find the total number of non leaf nodes present in a tree using recursion. We have to create a recursive function which takes in root of the tree as input and returns count of number of non leaf nodes present in a tree.

Expected Input and Output

Case 1. Tree having same weight on both the sides of root node (A Balanced Tree).
For example:

If the input tree is   
                    25
                  /    \
                 27     19
                / \     / \
              17  91   13 55 
The number of internal or non leaf nodes in this tree are 3

Case 2. Tree having only right children at every level (Right Skewed Tree) A right skewed tree is one in which all the nodes just have a right child at all the levels. For example:

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

If the input tree is       
                    1
                     \
                      2
                       \
                        3
                         \
                          4
                           \
                            5
The number of internal or non leaf nodes in this tree are 4

Case 3. Tree having just one node.
For example:

If the input tree is
                          15 
The number of internal or non leaf nodes in this tree are 1

Problem Solution

1. We can easily find the number of non leaf nodes present in any tree using recursion. A non leaf node is a node whose left or the right child is not NULL.
2. Non Leaf nodes are also known as Internal Nodes.
3. For a node to be an Internal Node, it needs to have at least one child. We just need to check this single condition to determine whether the node is a leaf node or a non leaf (internal) node.

Check this: Computer Science MCQs | Programming MCQs

Program/Source Code

Here is source code of the C Program to count the total number of non leaf nodes present in a given 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 to find the number of non leaf nodes in a Tree */

```
#include <stdio.h>
```
```
#include <stdlib.h>
```
```
 
```
```
struct node
```
```
{
```
```
    int info;
```
```
    struct node* left, *right;
```
```
 
```
```
};
```
```
 
```
```
/*
```
```
 * Function to create new nodes
```
```
 */
```
```
 
```
```
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);
```
```
}
```
```
 
```
```
/* 
```

 * Function to count number of leaf nodes

```
 */
```
```
 
```
```
int count = 0;
```
```
int nonleafnodes(struct node* newnode)
```
```
{
```
```
 
```
```
    if(newnode != NULL)
```
```
    {
```
```
        nonleafnodes(newnode->left);
```

        if((newnode->left != NULL) || (newnode->right != NULL))

```
        {
```
```
            count++;
```
```
        }
```
```
        nonleafnodes(newnode->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- Balanced Tree
```
```
 
```
```
 
```
```
                    25
```
```
                  /    \
```
```
                 27     19
```
```
                / \     / \
```
```
              17  91   13 55
```
```
 
```
```
    */
```

    printf("Number of non leaf nodes in first Tree are\t%d",nonleafnodes(newnode));

```
    printf("\n");
```
```
    count = 0;
```
```
 
```
```
    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("\n");
```

    printf("Number of non leaf nodes in second tree are\t%d",nonleafnodes(node));

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

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

```
 
```
```
                   15
```
```
    */
```
```
    printf("\n");
```

    printf("Number of non leaf nodes in third tree are\t%d",nonleafnodes(root));

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

Program Explanation

1. In this program we have used recursion to find the total number of non leaf nodes present in a tree. A non leaf Node is one whose left or the right child is not NULL.
2. We have created a function called nonleafnodes() which takes in root of the tree as a parameter and returns the total number of non leaf nodes it has.
3. The basic idea is to traverse the tree using any traversal so as to visit each and every node and check the condition for non leaf node for each node, that is what we have done in nonleafnodes() function.
4. In the nonleafnodes() function we have used the inorder traversal, by first traversing the left subtree, then instead of printing the root->data as a second step of inorder traversal, we have checked the nonleaf node condition and then at last we have traversed the right subtree by passing root->right as a parameter.

Runtime Test Cases

Number of non leaf nodes in first Tree are  3
 
Number of non leaf nodes in second tree are 4
 
Number of non leaf nodes in third tree are  0

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.

« Prev - C Program to Find Maximum Distance Between Two Nodes in a Binary Tree

» Next - C Program to Find the Summation of Node Values at Row or Level

Next Steps:

Get Free Certificate of Merit in Data Structure I
Participate in Data Structure I Certification Contest
Become a Top Ranker in Data Structure I
Take Data Structure I Tests
Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Related Posts:

Apply for Computer Science Internship
Buy Computer Science Books
Buy Programming Books
Apply for Information Technology Internship
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: