Jun 112012
 

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 Responses to “Counting leaf nodes of a Binary Tree”

Comments (1) Pingbacks (2)
  1. you can also add that one line.. how you can call this in main function. that’s where i got stucked.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)