Count of nodes in a Binary Tree whose child is its prime factors | JavaScript 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 ; Create Binary Tree as shown ; To save all prime numbers ; Print Count of all nodes having children as their factors
let N = 1000000 ; let prime = [ ] ; function SieveOfEratosthenes ( ) { let check = new Array ( N + 1 ) ; check . fill ( true ) ; for ( let p = 2 ; p * p <= N ; p ++ ) { if ( check [ p ] == true ) { prime . push ( p ) ; for ( let i = p * p ; i <= N ; i += p ) check [ i ] = false ; } } } class Node { constructor ( key ) { this . left = null ; this . right = null ; this . key = key ; } } function newNode ( key ) { let temp = new Node ( key ) ; return ( temp ) ; } function IsChilrenPrimeFactor ( parent , a ) { if ( prime [ a . key ] > 0 && ( parent . key % a . key == 0 ) ) return true ; else return false ; } function GetCount ( node ) { if ( node == null ) return 0 ; let q = [ ] ; let count = 0 ; q . push ( node ) ; while ( q . length > 0 ) { let temp = q [ 0 ] ; q . shift ( ) ; 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 ; } let 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 ( ) ; document . write ( GetCount ( root ) + " " ) ;