 ### C++ Program to count the Number of non leaf node in a binary tree.

C++ Program to count the number of non leaf node in binary tree.

Solution :

I have used Ubuntu software operating system to implement it, we also can use others.

Here, we are going to create a nodes with right and left pointers using structures in C++ in order to form a Binary tree.

1. We can find the number of non leaf nodes present in any tree using recursion easily. A non leaf node is that node whose left or the right child is not NULL.
2. For a node to be a Non -Leaf Node, it needs to have at least one child. So we  just need to check this single condition to determine whether the node is a leaf node or a non leaf node.

Input : Binary Tree

Output : Number of Non-Leaf Node in a Binary Tree In above diagram there are 3 non - leaf nodes that are 55, 21 and 80 .

Program/Code:

nonleaf.cpp-------------------------------------------------

#include <bits/stdc++.h>

using namespace std;

//node structure

struct Node {

int data;

struct Node* left;

struct Node* right;

};

//this function is used to allocates a new node with the given data and NULL left and right pointers.

struct Node* nn(int data)

{

struct Node* node = new Node;

node->data = data;

node->left = node->right = NULL;

return (node);

}

// this function to counts the number of non-leaf nodes in a binary tree

int count(struct Node* root)

{

// Base cases.

if (root == NULL || (root->left == NULL && root->right == NULL))

return 0;

// if root is not null then it is a non-leaf node exists

return 1 + count(root->left) + count(root->right);

}

//main function

int main()

{

struct Node* root = nn(55);

root->left = nn(21);

root->right = nn(80);

root->left->left =nn(9);

root->left->right = nn(29);

root->right->left =nn(76);

root->right->right = nn(91);

cout<<" Number of non- leaf nodes : "<<count(root);

return 0;

}

Output----------------------  