This is a C Program to calculate number of leaf nodes in a tree.

We are given a tree, and we have to write a C program to find the total number of leaf nodes present in a tree using recursion. We have to create a recursive function which takes in root of the tree as input and returns count of number of leaf nodes present in a tree.

**Case 1.Tree having same weight on both the sides of root node (A Balanced Tree).** For Example:

If the input tree is 25 / \ 27 19 / \ / \ 17 91 13 55 then number of leaf nodes in this tree will be 4

**Case 2. Tree having only right children at every level (Right Skewed Tree)**. A right skewed tree is one in which all the nodes just have a right child at all the levels. For example:

If the input tree is 1 \ 2 \ 3 \ 4 \ 5 then number of leaf nodes in this tree will be 1

**Case 3. Tree having just one node**

If the input tree is 15 then number of leaf nodes in this tree will be 1

We can easily find the number of leaf nodes present in any tree using recursion. A leaf node is a node whose left and right child are NULL. We just need to check this single condition to determine whether the node is a leaf node or a non leaf (internal) node.

Here is source code of the C Program to count the total number of leaf nodes present in a given tree. The program is successfully compiled and tested using Codeblocks gnu/GCC compiler on windows 10. The program output is also shown below.

`/* C Program to find the number of leaf nodes in a Tree */`

`#include <stdio.h>`

`#include <stdlib.h>`

`struct node`

`{`

int info;

struct node* left, *right;

};

`/*`

`* Function to create new nodes`

`*/`

struct node* createnode(int key)

`{`

struct node* newnode = (struct node*)malloc(sizeof(struct node));

newnode->info = key;

newnode->left = NULL;

newnode->right = NULL;

return(newnode);

`}`

`/*`

`* Function to count number of leaf nodes`

`*/`

int count = 0;

int leafnodes(struct node* newnode)

`{`

if(newnode != NULL)

`{`

leafnodes(newnode->left);

if((newnode->left == NULL) && (newnode->right == NULL))

`{`

`count++;`

`}`

leafnodes(newnode->right);

`}`

return count;

`}`

`/*`

`* Main Function`

`*/`

int main()

`{`

`/* Creating first Tree.*/`

struct node *newnode = createnode(25);

newnode->left = createnode(27);

newnode->right = createnode(19);

newnode->left->left = createnode(17);

newnode->left->right = createnode(91);

newnode->right->left = createnode(13);

newnode->right->right = createnode(55);

`/* Sample Tree 1- Balanced Tree`

`25`

`/ \`

`27 19`

`/ \ / \`

`17 91 13 55`

`*/`

printf("Number of leaf nodes in first Tree are\t%d\n",leafnodes(newnode));

count = 0;

struct node *node = createnode(1);

node->right = createnode(2);

node->right->right = createnode(3);

node->right->right->right = createnode(4);

node->right->right->right->right = createnode(5);

`/* Sample Tree 2- Right Skewed Tree (Unbalanced).`

`1`

`\`

`2`

`\`

`3`

`\`

`4`

`\`

`5`

`*/`

printf("\nNumber of leaf nodes in second tree are\t%d\n",leafnodes(node));

count = 0;

`/*Creating third Tree. */`

struct node *root = createnode(15);

`/* Sample Tree 3- Tree having just one root node.`

`15`

`*/`

printf("\nNumber of leaf nodes in third tree are\t%d",leafnodes(root));

return 0;

`}`

1. In this program we have used recursion to find the total number of leaf nodes present in a tree. A Leaf Node is one whose left and right child are NULL.

2. We have created a function called **leafnodes()** which takes in root of the tree as a parameter and returns the total number of leaf nodes it has.

3. The basic idea is to traverse the tree using any traversal so as to visit each and every node and check the condition for leaf node for each node, that is what we have done in leafnodes() function.

4. In the leafnodes() function we have used the inorder traversal, by first traversing the left subtree, then instead of printing the root->data as a second step of inorder traversal, we have checked the leaf node condition and then at last we have traversed the right subtree by passing root->right as a parameter.

Number of leaf nodes in first Tree are 4 Number of leaf nodes in second tree are 1 Number of leaf nodes in third tree are 1

**Sanfoundry Global Education & Learning Series – 1000 C Programs.**

Here’s the list of Best Books in C Programming, Data-Structures and Algorithms

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Practice Computer Science MCQs
- Check Programming Books
- Practice Programming MCQs
- Check Data Structure Books
- Check Computer Science Books