Checking if a number is fibonacci
June 11, 2012
Has Path Sum (binary tree)
June 11, 2012

Counting leaf nodes of a Binary Tree

Write a function to count the leaf nodes of a binary tree.

Solution:

Problems of Binary tree can be easily solved using recursion. Because the child nodes of a Binary tree are also Binary tree in themselves.

Algorithm:

The below algorithm does it recursively.

If (current node is a leaf node)
    leaf_count += 1;
else
    leaf_cout += leaf_count of left sub tree + leaf_count of right sub tree

C Program:

Here is a C program to do the same..

    struct node{
         int data;
         node* lptr;
         node* rptr;
    };
    /** return the number of leaf nodes in the tree whose root is at r */
    int count_leaf(node *r){
        if(r){
            return (!r->lptr && !r->rptr) ?
                1 :
                count_leaf(r->lptr) + count_leaf(r->rptr);
        }else{
            return 0;
         }
    }

3 Comments

  1. […] earlier questions related to tree, “Counting number of leaf nodes” and “Has-Path sum problem“, I have written that tree algorithms are better […]

  2. […] I have written a post to count the number of leaf nodes in the binary tree. The function to count the non-leaf nodes will be complement of the function to counting leaf […]

  3. Anand says:

    you can also add that one line.. how you can call this in main function. that’s where i got stucked.

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *