C Program to Count Leaf Nodes in a Binary Tree

  • 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
Posted by
Labels: