C++ Program to Count all the Internal Nodes in a given Binary Search Tree

«
»

This is a C++ Program for counting the total number of internal nodes present in a given Binary Search Tree.

Problem Description

We will be given a Binary Search Tree and we have to create a C++ program which counts the total number of non-leaf nodes i.e. Internal Nodes present in it using recursion. An internal node is one which has at least one children.

Expected Input and Output

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

advertisement
                    25
                  /    \
                 19     29
                / \     / \
              17  20   27 55

Output: 3

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

                    1
                     \
                      2
                       \
                        3
                         \
                          4
                           \
                            5

Output: 4

advertisement

Case 3. Tree having just one node

              15

Output: 0

advertisement
Problem Solution

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

In this program we have used recursion to find the total number of internal nodes present in a tree.
2. A internal Node is one whose left or the right child is not NULL. We have created a function called internalnodes() which takes in root of the tree as a parameter and returns the total number of internal 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 internal node for each node, that is what we have done in internalnodes() function.
4. In the internalnodes() 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 internal 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 internal nodes in first Tree are      3
 
Number of internal nodes in second tree are     4
 
Number of internal 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.

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