Jun 122012
 

Write a function that will return the number of non-leaf nodes in a binary tree. For example: The below binary tree

            A 
           / \ 
          B   C 
         / \ 
        D   E

has 3 leaf nodes (C, D & E) and 2 non-leaf nodes(A & B).

Solution:

Earlier, 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 nodes.

We will again use recursion, as we do in most of the questions related to Binary Tree.

Algorithm:

If (current node is a leaf node or it is NULL)
    return 0;
else
    return (1 + non_leaf_count of left sub tree + non_leaf_count of right sub tree);

Code:

Here is a C program to do the same..

    struct Node{
         int data;
         Node* lptr;
         Node* rptr;
    };

    /** return the number of non-leaf nodes in the tree whose root is at r */
    int count_non_leaf(Node *r)
    {

        /* If r is either leaf node or NULL */
        if(r==NULL || (r->lptr == NULL && r->rptr == NULL) )
        {
            return 0;
        }
        else
        {
            return (1 + count_non_leaf(r->lptr) + count_non_leaf(r->rptr) );
        }
    }

 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)