Count Leaf Nodes in a Binary Tree

By | October 24, 2015

Counting Leaf Nodes in a Binary Tree.

Count Leaf Nodes in a Binary Tree problem Statement:

Given a Binary Tree, we need to output the number of leaf nodes in it.
A leaf node is one, which had both its left and right child NULL.

Counting Leaf Nodes in a Binary Tree example:

Given this Binay Tree as input:

             80                 
           /     \        
          60      110     
         /  \    /  \     
       35   40  85   130

For this tree shown above the answer should be 4.

Counting Leaf Nodes in a Binary Tree Solution:

We simply check if both the children of a node are NULL, if yes we return 1, else we return 0

Algorithm to Count Leaf Nodes in a Binary Tree :

  1. If the root is null ( the tree is empty ) then return 0.
  2. Else
    1. Check if the present node is leaf,
      If yes then return 1
    2. Count leaves the left subtree
      leafsCount(root->left).
    3. Count leaves the right subtree
      leafsCount(root->right).
    4. Return the sum of counts from point 2 and 3 above.

Count Leaf Nodes in a Binary Tree Solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure for each node of the tree*/
struct node
{
   int data;
   node *right,*left;
};


/*Function that allocates memory for
each new node and initialises it*/
node * newNode(int data)
{
   node *temp=new node;
   temp->data=data;
   temp->left=NULL;
   temp->right=NULL;
   
   return temp;
}

/*The function that gives the number 
of leaf nodes in the tree*/
int LeafCount(node *root)
{
   /*Base case when the tree is NULL*/
   if(!root)
      return 0;
   
   /*Check if the present node is 
   a leaf or not*/	
   if(!root->left && !root->right)
   	  return 1;
   /*we reach here, when the root
   /node is not NULL and is not a 
   leaf*/	  
   return (LeafCount(root->left) +LeafCount(root->right));
}

int main()
{
  /*        
  We are making the following tree
  	     80                 
           /     \        
          60      110     
         /  \    /  \     
       35   40  85   130
  This is a BST.
  */
  node *root         = newNode(80);
  root->left         = newNode(60);
  root->right        = newNode(110);
  root->left->left   = newNode(35);
  root->left->right  = newNode(40);   
  root->right->left  = newNode(85);  
  root->right->right = newNode(130);  
  
  cout<<"The Number of leaf nodes is: \n";  
  cout<<LeafCount(root);
  
  return 0;
}

 Output:

The Number of leaf nodes is: 
4

Time Complexity: O(N) where N is the total number of nodes