ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Print the number of leaf nodes in a binary tree

prodevelopertutorial March 30, 2020

In this chapter we shall print the number of leaf nodes in a binary tree.

 

Problem Statement:

You are given the root node of the tree. You need to return the total number of leaf nodes present in that tree.

 

Example:

 

Consider the below tree

Print the number of leaf nodes in a binary tree

 

In the above tree, there are 4 leaf nodes.

 

d, e, f, g

 

You need to write a program to print the same.

 

So from the image above, we can see that, the nodes whose left child is null and right child is also null, such node is called as a leaf node.

 

So we can write a recursive function to check all the nodes in a tree, if it is a leaf node or not.

Solution in C++

#include <iostream>
#include <stack>
#include <map>
using namespace std;

// structure to hold binary tree node
struct Node
{
    int data;
    Node *left, *right;

    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};


int sum = 0;

void get_number_of_leaf_nodes(Node *root) 
{ 
    if (!root) 
        return; 
      
    if (!root->left && !root->right) 
    { 
        sum++;
        return ; 
    } 

    if (root->left) 
       get_number_of_leaf_nodes(root->left); 
          
    if (root->right) 
       get_number_of_leaf_nodes(root->right); 
}  


  
int main()  
{  
    Node* root = nullptr;
    /* Binary tree:
              16
            /   \
           /     \
          10      25
         /  \    /  \
        /    \  /    \
       7    15 18     30

    */

    root = new Node(16);
    root->left = new Node(10);
    root->right = new Node(25);
    root->left->left = new Node(7);
    root->left->right = new Node(15);
    root->right->left = new Node(18);
    root->right->right = new Node(30);

    get_number_of_leaf_nodes(root);

    cout<<"The number of leaf nodes are "<<sum<<endl;

    return 0;  
}  

 

Output:

The number of leaf nodes are 4

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io