Count of nodes in a Binary Tree whose child is its prime factors | C ++ program for Counting nodes whose immediate children are its factors ; To store all prime numbers ; Create a boolean array " prime [ 0 . . N ] " and initialize all its entries as true . A value in prime [ i ] will finally be false if i is Not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it numbers which are multiples of p and are less than p ^ 2 are already marked . ; A Tree node ; Utility function to create a new node ; Function to check if immediate children of a node are its factors or not ; Function to get the count of full Nodes in a binary tree ; If tree is empty ; Initialize count of full nodes having children as their factors ; If only right child exist ; If only left child exist ; Both left and right child exist ; Check for left child ; Check for right child ; Driver Code ; Create Binary Tree as shown ; To save all prime numbers ; Print Count of all nodes having children as their factors
#include <bits/stdc++.h> NEW_LINE using namespace std ; int N = 1000000 ; vector < int > prime ; void SieveOfEratosthenes ( ) { bool check [ N + 1 ] ; memset ( check , true , sizeof ( check ) ) ; for ( int p = 2 ; p * p <= N ; p ++ ) { if ( check [ p ] == true ) { prime . push_back ( p ) ; for ( int i = p * p ; i <= N ; i += p ) check [ i ] = false ; } } } struct Node { int key ; struct Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return ( temp ) ; } bool IsChilrenPrimeFactor ( struct Node * parent , struct Node * a ) { if ( prime [ a -> key ] && ( parent -> key % a -> key == 0 ) ) return true ; else return false ; } unsigned int GetCount ( struct Node * node ) { if ( ! node ) return 0 ; queue < Node * > q ; int count = 0 ; q . push ( node ) ; while ( ! q . empty ( ) ) { struct Node * temp = q . front ( ) ; q . pop ( ) ; if ( temp -> left == NULL && temp -> right != NULL ) { if ( IsChilrenPrimeFactor ( temp , temp -> right ) ) count ++ ; } else { if ( temp -> right == NULL && temp -> left != NULL ) { if ( IsChilrenPrimeFactor ( temp , temp -> left ) ) count ++ ; } else { if ( temp -> left != NULL && temp -> right != NULL ) { if ( IsChilrenPrimeFactor ( temp , temp -> right ) && IsChilrenPrimeFactor ( temp , temp -> left ) ) count ++ ; } } } if ( temp -> left != NULL ) q . push ( temp -> left ) ; if ( temp -> right != NULL ) q . push ( temp -> right ) ; } return count ; } int main ( ) { Node * root = newNode ( 10 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 18 ) ; root -> right -> right = newNode ( 12 ) ; root -> right -> left -> left = newNode ( 2 ) ; root -> right -> left -> right = newNode ( 3 ) ; root -> right -> right -> left = newNode ( 3 ) ; root -> right -> right -> right = newNode ( 14 ) ; root -> right -> right -> right -> left = newNode ( 7 ) ; SieveOfEratosthenes ( ) ; cout << GetCount ( root ) << endl ; return 0 ; }