# 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 :

- If the root is null ( the tree is empty ) then return 0.
- Else
- Check if the present node is leaf,

If yes then return 1 - Count leaves the left subtree

leafsCount(root->left). - Count leaves the right subtree

leafsCount(root->right). - Return the sum of counts from point 2 and 3 above.

- Check if the present node is leaf,

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