Home Trees Give an algorithm to find the number of leaves in a binary tree.

# Give an algorithm to find the number of leaves in a binary tree.

0 comment

Question: Given the root pointer to a binary tree, find the number of leaves.

Input: Sample Tree (Pointer to node 1 is given). Find the number of leaves. Output: Number of leaves = 4

According to the definition, the set of all nodes whose both left and right child are null, are known as leaf nodes.

In the above example, we have the nodes – 7, 9, 5, 4 as the leaf nodes.

We can perform a level order traversal and count the number of nodes, who have their right child and left child as null. Return the count in the end.

#include<stdio.h>
#include<malloc.h>

struct binaryTreeNode{
int data;
struct binaryTreeNode * left;
struct binaryTreeNode * right;
};

int numberOfLeaves(struct binaryTreeNode * root)
{
// Level order traversal
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;

// Maintain a count
int count = 0;

if(root == NULL)
return 0;

Q = enQueue(Q, root);
while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;

// Now check if the node is a leaf node
if(temp -> left == NULL && temp -> right == NULL)
{
// This means a leaf node
count++;
}

Q = deQueue(Q);
if(temp -> left)
Q = enQueue(Q, temp -> left);
if(temp -> right)
Q = enQueue(Q, temp -> right);
}
// Delete the queue
free(Q);

// Now return the count
return count;
}


Time Complexity:- O(n)
Space Complexity:- O(n)

Ideone link for the sample program:- http://ideone.com/umTait

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More