# 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