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----------------------
Comments