# Count leaf nodes and non leaf nodes of binary tree

In computer science, a **binary tree** is a tree **data structure** in which each node has **at most two children**, which are referred to as the left child and the right child.

A binary tree is made of nodes, where each node contains a “**left**” reference, a “**right**” reference, and a data element. The topmost node in the tree is called the **root**. Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a **parent**. On the other hand, each node can be connected to arbitrary number of nodes, called **children**. Nodes with no children are called **leaves**, or **external nodes**. Nodes which are not leaves are called **internal nodes (non-leaf nodes)**. Nodes with the same parent are called siblings.

This program shows how to count leaf nodes and non-leaf nodes of binary tree.

As a pre summary, we are going to calculate the leaf nodes and non-leaf nodes seperately as functions.

So let’s start with calculating the leaf nodes.

## Counting leaf nodes of a Binary Tree

**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:**

We are going to need a recursive fucntion. Because we want to walk through all the nodes to see if it is a leaf or not, and we are going to understand it with the information that if that node has a child or not.

So here is the pseudo algorithm:

1 2 3 4 |
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 |

**Program:**

Here is the C program to do same.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// This struct is going to represent the nodes. // In a regular node, we are going to have a data as integer, and two pointers that points left and right childs of the node. struct treeNode{ int data; treeNode* lptr; treeNode* rptr; }; // return the number of leaf nodes in the tree whose root is at "root" int count_leaf(treeNode *root){ if(root){ return (!root->lptr && !root->rptr) ? 1 : count_leaf(root->lptr) + count_leaf(root->rptr); }else{ return 0; } } |

Let’s investigate the function.

It is going to return an integer number, and it is taking a node as an argument. In the function body, we have an if-else statement, and in the if statement we have another if-else statement (a cooler one).

1 |
return (!root->lptr && !root->rptr) ? 1 : count_leaf(root->lptr) + count_leaf(root->rptr); |

This return statement is stating that, if right and left childs are absent, this means it is a leaf, so return 1 as an integer value, but if any of them has a child, we need to go further, so we are calling our function again for left and right childs.

## Non-leaf nodes of a binary tree

**Question:**

Write a function that will return the number of non-leaf nodes in a binary tree.

**Solution:**

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:**

1 2 3 4 |
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 the C code to do the same.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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) ); } } |

You can find the code at my Gist.

Really helped my homework. Just wanted to thank you.