Count of nodes in a Binary Tree whose child is its prime factors | Java 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
import java . util . * ; class GFG { static int N = 1000000 ; static Vector < Integer > prime = new Vector < Integer > ( ) ; static void SieveOfEratosthenes ( ) { boolean [ ] check = new boolean [ N + 1 ] ; Arrays . fill ( check , true ) ; for ( int p = 2 ; p * p <= N ; p ++ ) { if ( check [ p ] == true ) { prime . add ( p ) ; for ( int i = p * p ; i <= N ; i += p ) check [ i ] = false ; } } } static class Node { int key ; Node left , right ; } ; static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = temp . right = null ; return ( temp ) ; } static boolean IsChilrenPrimeFactor ( Node parent , Node a ) { if ( prime . get ( a . key ) > 0 && ( parent . key % a . key == 0 ) ) return true ; else return false ; } static int GetCount ( Node node ) { if ( node == null ) return 0 ; Queue < Node > q = new LinkedList < > ( ) ; int count = 0 ; q . add ( node ) ; while ( ! q . isEmpty ( ) ) { Node temp = q . peek ( ) ; q . remove ( ) ; 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 . add ( temp . left ) ; if ( temp . right != null ) q . add ( temp . right ) ; } return count ; } public static void main ( String [ ] args ) { 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 ( ) ; System . out . print ( GetCount ( root ) + "NEW_LINE"); } }