Count half nodes in a Binary tree ( Iterative and Recursive ) | C ++ program to count half nodes in a Binary Tree ; A binary tree Node has data , pointer to left child and a pointer to right child ; Function to get the count of half Nodes in a binary tree ; Helper function that allocates a new Node with the given data and NULL left and right pointers . ; Driver program ; 2 / \ 7 5 \ \ 6 9 / \ / 1 11 4 Let us create Binary Tree shown in above example
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; unsigned int gethalfCount ( struct Node * root ) { if ( root == NULL ) return 0 ; int res = 0 ; if ( ( root -> left == NULL && root -> right != NULL ) || ( root -> left != NULL && root -> right == NULL ) ) res ++ ; res += ( gethalfCount ( root -> left ) + gethalfCount ( root -> right ) ) ; return res ; } struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } int main ( void ) { struct Node * root = newNode ( 2 ) ; root -> left = newNode ( 7 ) ; root -> right = newNode ( 5 ) ; root -> left -> right = newNode ( 6 ) ; root -> left -> right -> left = newNode ( 1 ) ; root -> left -> right -> right = newNode ( 11 ) ; root -> right -> right = newNode ( 9 ) ; root -> right -> right -> left = newNode ( 4 ) ; cout << gethalfCount ( root ) ; return 0 ; }