Counting 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.

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

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;
         }
    }