Non-leaf nodes of a binary tree

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