logo
  • Home
  • Test & Rank
  • About
  • Training
  • Programming
  • CS
  • IT
  • IS
  • ECE
  • EEE
  • EE
  • Civil
  • Mechanical
  • Chemical
  • Metallurgy
  • Instrumentation
  • Aeronautical
  • Aerospace
  • Biotechnology
  • Mining
  • Marine
  • Agriculture
  • MCA
  • BCA
  • Internship
  • Jobs
  • Contact

Questions & Answers

C Interview Questions
C++ Questions
Linux MCQs
C# Quiz
Java MCQs
JavaScript MCQs
SAN Questions
PHP Questions
Python Quiz

Computer Science Questions

Operating System Quiz
Computer Architecture MCQs
Software Architecture MCQs
Software Engineering MCQs
Artificial Intelligence MCQs
LISP Programming MCQs
Database Management MCQs
Computer Network MCQs
Microprocessor MCQs

C Programming Examples

Simple C Programs
C - Arrays
C - Matrix
C - Strings
C - Bitwise Operations
C - Linked Lists
C - Stacks & Queues
C - Searching & Sorting
C - Trees
C - Strings
C - File Handling
C - Mathematical Functions
C - Puzzles & Games
C Programs - Recursion
C Programs - No Recursion

Java Algorithms

Java - Numerical Problems
Java - Combinatorial Problems
Java - Graph Problems
Java - Hard Graph Problems
Java - Computation Geometry
Java - Sets & Strings
Java - Data-Structures
Java - Collection API Problems

C++ Algorithms

C++ - Numerical Problems
C++ - Combinatorial Problems
C++ - Graph Problems
C++ - Hard Graph Problems
C++ - Computation Geometry
C++ - Sets & Strings
C++ - Data-Structures
C++ - STL Library

C Algorithms

C - Numerical Problems
C - Combinatorial Problems
C - Graph Problems
C - Hard Graph Problems
C - Computation Geometry
C - Sets & Strings
C - Data-Structures

« Prev Page
Next Page »

C Program to Count Number of Non Leaf Nodes of a given Tree

Posted on April 10, 2013 by Manish

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:

advertisement
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:

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:

advertisement
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.

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.

  1. /* C Program to find the number of non leaf nodes in a Tree */
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. struct node
  6. {
  7.     int info;
  8.     struct node* left, *right;
  9.  
  10. };
  11.  
  12. /*
  13.  * Function to create new nodes
  14.  */
  15.  
  16. struct node* createnode(int key)
  17. {
  18.     struct node* newnode = (struct node*)malloc(sizeof(struct node));
  19.     newnode->info = key;
  20.     newnode->left = NULL;
  21.     newnode->right = NULL;
  22.  
  23.     return(newnode);
  24. }
  25.  
  26. /* 
  27.  * Function to count number of leaf nodes
  28.  */
  29.  
  30. int count = 0;
  31. int nonleafnodes(struct node* newnode)
  32. {
  33.  
  34.     if(newnode != NULL)
  35.     {
  36.         nonleafnodes(newnode->left);
  37.         if((newnode->left != NULL) || (newnode->right != NULL))
  38.         {
  39.             count++;
  40.         }
  41.         nonleafnodes(newnode->right);
  42.     }
  43.     return count;
  44.  
  45. }
  46.  
  47. /*
  48.  * Main Function
  49.  */
  50.  
  51. int main()
  52. {
  53.    /* Creating first Tree.*/
  54.  
  55.     struct node *newnode = createnode(25);
  56.     newnode->left = createnode(27);
  57.     newnode->right = createnode(19);
  58.     newnode->left->left = createnode(17);
  59.     newnode->left->right = createnode(91);
  60.     newnode->right->left = createnode(13);
  61.     newnode->right->right = createnode(55);
  62.  
  63.     /* Sample Tree 1- Balanced Tree
  64.  
  65.  
  66.                     25
  67.                   /    \
  68.                  27     19
  69.                 / \     / \
  70.               17  91   13 55
  71.  
  72.     */
  73.     printf("Number of non leaf nodes in first Tree are\t%d",nonleafnodes(newnode));
  74.     printf("\n");
  75.     count = 0;
  76.  
  77.     struct node *node = createnode(1);
  78.     node->right = createnode(2);
  79.     node->right->right = createnode(3);
  80.     node->right->right->right = createnode(4);
  81.     node->right->right->right->right = createnode(5);
  82.  
  83.     /* Sample Tree 2-   Right Skewed Tree (Unbalanced).
  84.  
  85.                     1
  86.                      \
  87.                       2
  88.                        \
  89.                         3
  90.                          \
  91.                           4
  92.                            \
  93.                             5
  94.     */
  95.     printf("\n");
  96.     printf("Number of non leaf nodes in second tree are\t%d",nonleafnodes(node));
  97.     printf("\n");
  98.     count = 0;
  99.  
  100.     /*Creating third Tree. */
  101.  
  102.     struct node *root = createnode(15);
  103.  
  104.     /* Sample Tree 3-  Tree having just one root node.
  105.  
  106.                    15
  107.     */
  108.     printf("\n");
  109.     printf("Number of non leaf nodes in third tree are\t%d",nonleafnodes(root));
  110.  
  111.     return 0;
  112. }
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.

advertisement
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 Reference 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 Page - C Program to Copy File into Another File
» Next Page - C Program to find Next higher Value of N with same 1’s

« Linux Kernel Internals Training – II – Process Management
C Program to find Next higher Value of N with same 1’s »
advertisement

Deep Dive @ Sanfoundry:

  1. C Programming Examples on Graph Problems & Algorithms
  2. C++ Programming Examples on Graph Problems & Algorithms
  3. C++ Programming Examples on Data-Structures
  4. C Programming Examples using Recursion
  5. Python Programming Examples on Graphs
  6. C Programming Examples without using Recursion
  7. Python Programming Examples on Linked Lists
  8. C Programming Examples on Linked List
  9. Python Programming Examples on Trees
  10. C Programming Examples on Trees
Manish Bhojasia
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Facebook | Twitter

Best Careers

Developer Tracks
SAN Developer
Linux Kernel Developer
Linux Driver Developer
Linux Network Developer

Live Training Photos
Mentoring
Software Productivity
GDB Assignment
Sanfoundry is No. 1 choice for Deep Hands-ON Trainings in SAN, Linux & C, Kernel Programming. Our Founder has trained employees of almost all Top Companies in India such as VMware, Citrix, Oracle, Motorola, Ericsson, Aricent, HP, Intuit, Microsoft, Cisco, SAP Labs, Siemens, Symantec, Redhat, Chelsio, Cavium, ST-Micro, Samsung, LG-Soft, Wipro, TCS, HCL, IBM, Accenture, HSBC, Mphasis, Tata-Elxsi, Tata VSNL, Mindtree, Cognizant and Startups.

Best Trainings

SAN I - Technology
SAN II - Admin
Linux Fundamentals
Advanced C Training
Linux-C Debugging
System Programming
Network Programming
Linux Threads
Kernel Programming
Kernel Debugging
Linux Device Drivers

Best Reference Books

Computer Science Books
Algorithm & Programming Books
Electronics Engineering Books
Electrical Engineering Books
Chemical Engineering Books
Civil Engineering Books
Mechanical Engineering Books
Industrial Engineering Books
Instrumentation Engg Books
Metallurgical Engineering Books
All Stream Best Books

Questions and Answers

1000 C Questions & Answers
1000 C++ Questions & Answers
1000 C# Questions & Answers
1000 Java Questions & Answers
1000 Linux Questions & Answers
1000 Python Questions
1000 PHP Questions & Answers
1000 Hadoop Questions
Cloud Computing Questions
Computer Science Questions
All Stream Questions & Answers

India Internships

Computer Science Internships
Instrumentation Internships
Electronics Internships
Electrical Internships
Mechanical Internships
Industrial Internships
Systems Internships
Chemical Internships
Civil Internships
IT Internships
All Stream Internships

About Sanfoundry

About Us
Copyright
Terms
Privacy Policy
Jobs
Bangalore Training
Online Training
Developers Track
Mentoring Sessions
Contact Us
Sitemap
© 2011 Sanfoundry. All Rights Reserved.