- Write a program in C to count number of leaf nodes in a given binary tree.
- Write a function to find number of leaf node using recursion.

Given a binary tree, we have to **count number of leaf nodes in tree**. A node is a leaf node, if it's left children and right children are NULL. Here, we will use recursion approach to **count leaf nodes**. We will traverse the binary tree using pre Order traversal and find the leaf nodes in left and right sub tree recursively.

**Algorithm to count leaf nodes in a binary tree**

Let "root" be the root pointer of a binary tree.

- If root is NULL, return zero.
- If root is a leaf node, return 1. To determine a leaf node check if both left and right children's are NULL.
- Recursively, calculate the count of leaf nodes in left and right sub tree.
- Return the sum of leaf node count of left and right sub tree.

**Time Complexity**: O(n)

**Space Complexity**: O(1) without considering the internal stack space used for recursive calls, otherwise O(n).

In this program, we will use a recursive function "countLeafNode" which does pre order traversal and count the number of leaf nodes by implementing above mentioned recursive algorithm.

/* Returns the count of leaf nodes in a binary tree */ int countLeafNode(struct node *root){ /* Empty(NULL) Tree */ if(root == NULL) return 0; /* Check for leaf node */ if(root->left == NULL && root->right == NULL) return 1; /* For internal nodes, return the sum of leaf nodes in left and right sub-tree */ return countLeafNode(root->left) + countLeafNode(root->right); }

## C program to count leaf nodes in a binary tree.

#include <stdio.h> struct node { int data; struct node *left; struct node *right; }; struct node* getNewNode(int data) { /* dynamically allocate memory for a new node */ struct node* newNode = (struct node*)malloc(sizeof(struct node)); /* populate data in new Node */ newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; } /* This function returns below 1 / \ 2 3 / \ / \ 4 5 6 7 / 8 */ struct node* generateBTree(){ // Root Node struct node* root = getNewNode(1); // Level 2 nodes root->left = getNewNode(2); root->right = getNewNode(3); // Level 3 nodes root->left->left = getNewNode(4); root->left->right = getNewNode(5); root->right->left = getNewNode(6); root->right->right = getNewNode(7); // Level 4 nodes root->left->left->left = getNewNode(8); return root; } /* Returns the count of leaf nodes in a binary tree */ int countLeafNode(struct node *root){ /* Empty(NULL) Tree */ if(root == NULL) return 0; /* Check for leaf node */ if(root->left == NULL && root->right == NULL) return 1; /* For internal nodes, return the sum of leaf nodes in left and right sub-tree */ return countLeafNode(root->left) + countLeafNode(root->right); } int main() { struct node *root = generateBTree(); /* Print number of lead nodes */ printf("Number of leaf Node : %d", countLeafNode(root)); getchar(); return 0; }Output

Number of leaf Node : 4