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