 ### c++ program to count number of half node present in binary tree without using recursion.

/*HALF NODE  means the nodes in a binary tree which have only one child .
Here is how we can count the number of half nodes present in a binary tree  using c++ program.

1. Create an empty queue and put the root node in it.
2.In while loop till the queue is not empty do the following.
2.1 Pop the node present in the queue and process it.
2.1.1 If the node has only one child increment the counter count by one i.e count++.
2.2 Push the left child node into the queue if present.
2.3 Push right child into the node if present.

now the program .*/
___________________________________________________________________________________________________________________________

#include<iostream.h>
#include<conio.h>
#include "queue.h"   /*  created header file using template /*

/* In a binary tree the nodes have two parts data part and pointer parts. Two pointers are present to to point to left and right child if present.*/

struct node
{ int data;
node *left,*right;
};

int counthalfnode(node *t )
{
/* If tree is empty*/

if (!t)
return 0;

/*Initialize count of half nodes*/

int count=0;

queue<node *> q;
q.push(t);
while (!q.empty())
struct node *temp = q.front();
q.pop();

if (!temp->left && temp->right ||
temp->left && !temp->right)
count++;

if (temp->left != NULL)
q.push(temp->left);
if (temp->right != NULL)
q.push(temp->right);
return count;
}

/* function to create node */

node * createnode(int a)
node *child =new node;
child ->data=a;
child->left=NULL;
child->right=NULL;
return (child);
}

/* above function create node and both pointers points to NULL*/

void main()
{ /*we create a tree like below*/

/*                 4
/
5        3

2           8
/           /
1          9      7
*/
node *root = createnode(4);
root->left= createnode(5);
root->right= createnode(3);
root->left->right = createnode(2);
root->left->right->left = createnode(1);
root->right->right =createnode(8);
root->right->right->left = createnode(9);
root->right->right->left = createnode(7);
int c;
c=counthalfnode(root);
cout<<"NUMBER OF HALF NODE PRESENT IS: "<<c;
getch();
}

___________________________________________________________________________________________________________________________

output: NUMBER OF HALF NODE PRESENT IS 3

___________________________________________________________________________________________________________________________ 