Number of subtrees having odd count of even numbers | C implementation to find number of subtrees having odd count of even numbers ; A binary tree Node ; Helper function that allocates a new Node with the given data and NULL left and right pointers . ; Returns count of subtrees having odd count of even numbers ; base condition ; count even nodes in left subtree ; Add even nodes in right subtree ; Check if root data is an even number ; if total count of even numbers for the subtree is odd ; Total count of even nodes of the subtree ; A wrapper over countRec ( ) ; Driver program to test above ; binary tree formation ; 2 ; / \ ; 1 3 ; / \ / \ ; 4 10 8 5 ; / ; 6
#include <bits/stdc++.h> NEW_LINE struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } int countRec ( struct Node * root , int * pcount ) { if ( root == NULL ) return 0 ; int c = countRec ( root -> left , pcount ) ; c += countRec ( root -> right , pcount ) ; if ( root -> data % 2 == 0 ) c += 1 ; if ( c % 2 != 0 ) ( * pcount ) ++ ; return c ; } int countSubtrees ( Node * root ) { int count = 0 ; int * pcount = & count ; countRec ( root , pcount ) ; return count ; } int main ( ) { struct Node * root = newNode ( 2 ) ; root -> left = newNode ( 1 ) ; root -> right = newNode ( 3 ) ; root -> left -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 10 ) ; root -> right -> left = newNode ( 8 ) ; root -> right -> right = newNode ( 5 ) ; root -> left -> right -> left = newNode ( 6 ) ; printf ( " Count ▁ = ▁ % d " , countSubtrees ( root ) ) ; return 0 ; }