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

This is a C++ Program for counting the total number of leaf 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 leaf nodes present in it using recursion. A leaf node is one which has no child. It is also known as internal node.

Expected Input and Output

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

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

Output: 4

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

advertisement
advertisement
                    1
                     \
                      2
                       \
                        3
                         \
                          4
                           \
                            5

Output: 1

Case 3. Tree having just one node

Note: Join free Sanfoundry classes at Telegram or Youtube
              15

Output: 1

Problem Solution

We can easily find the number of leaf nodes present in any tree using recursion. A leaf node is a node whose left and right child are 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 leaf 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.

advertisement
  1. /* C++ Program to find the number of leaf 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. };
  10. int count = 0;
  11. class BST
  12. {
  13.     public:
  14.         /*
  15.          * Function to create new nodes
  16.          */
  17.         struct node *createnode(int key)
  18.         {
  19.             struct node *newnode = new node;
  20.             newnode->info = key;
  21.             newnode->left = NULL;
  22.             newnode->right = NULL;
  23.             return(newnode);
  24.         }
  25.         int leafnodes(struct node *newnode)
  26.         {
  27.             if(newnode != NULL)
  28.             {
  29.                 leafnodes(newnode->left);
  30.                 if((newnode->left == NULL) && (newnode->right == NULL))
  31.                 {
  32.                     count++;
  33.                 }
  34.                 leafnodes(newnode->right);
  35.             }
  36.             return count;
  37.         }
  38. };
  39. int main()
  40. {
  41.    /* Creating first Tree. */
  42.     BST t1,t2,t3;
  43.     struct node *newnode = t1.createnode(25);
  44.     newnode->left = t1.createnode(19);
  45.     newnode->right = t1.createnode(29);
  46.     newnode->left->left = t1.createnode(17);
  47.     newnode->left->right = t1.createnode(20);
  48.     newnode->right->left = t1.createnode(27);
  49.     newnode->right->right = t1.createnode(55);
  50.     /* Sample Tree 1. Balanced Tree
  51.      *               25
  52.      *             /    \
  53.      *            19    29
  54.      *           / \     / \
  55.      *         17  20   27 55
  56.      */
  57.     cout<<"Number of leaf nodes in first Tree are\t"<<t1.leafnodes(newnode)<<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 leaf nodes in second tree are\t"<<t2.leafnodes(node)<<endl;
  78.     count = 0;
  79.  
  80.     /*Creating third Tree. */
  81.     struct node *root = t3.createnode(15);
  82.     /* Sample Tree 3-  Tree having just one root node.
  83.      *              15
  84.      */
  85.     cout<<"\nNumber of leaf nodes in third tree are\t"<<t3.leafnodes(root);
  86.     return 0;
  87. }
Program Explanation

1. In this program we have used recursion to find the total number of leaf nodes present in a tree.
2. A leaf Node is one whose left and right child are NULL. We have created a function called leafnodes() which takes in root of the tree as a parameter and returns the total number of 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 leaf node for each node, that is what we have done in leafnodes() function.
4. In the leafnodes() 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 leaf node condition and then at last we have traversed the right subtree by passing root->right as a parameter.

Runtime Test Cases
Number of leaf nodes in first Tree are  4
 
Number of leaf nodes in second tree are 1
 
Number of leaf nodes in third tree are  1

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement

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

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.