A Question A Day: Count leaf nodes in a Binary Tree

MCN Professionals | Interview Question of the day

Today's Question:

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

Interview Questions Archive:

                  To see all the questions in the category, click here...

------------------------------------------------------------------------------------------------------------