Print all Coprime path of a Binary Tree | A Tree node ; Utility function to create a new node ; Vector to store all the prime numbers ; Function to store all the prime numbers in an array ; Create a boolean array " prime [ 0 . . N ] " and initialize all the entries in it 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 . ; Function to check whether Path is Co - prime or not ; Iterating through the array to find the maximum element in the array ; Incrementing the variable if any of the value has a factor ; If not co - prime ; Function to print a Co - Prime path ; Function to find co - prime paths of binary tree ; Base case ; Store the value in path vector ; Recursively call for left sub tree ; Recursively call for right sub tree ; Condition to check , if leaf node ; Condition to check , if path co - prime or not ; Print co - prime path ; Remove the last element from the path vector ; Function to find Co - Prime paths In a given binary tree ; To save all prime numbers ; Function call ; Create Binary Tree as shown ; Print Co - Prime Paths
class Node { constructor ( key ) { this . left = null ; this . right = null ; this . key = key ; } } function newNode ( key ) { let temp = new Node ( key ) ; return ( temp ) ; } 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 ; } } } function isPathCo_Prime ( path ) { let max = 0 ; for ( let x = 0 ; x < path . length ; x ++ ) { if ( max < path [ x ] ) max = path [ x ] ; } for ( let i = 0 ; i * prime [ i ] <= parseInt ( max / 2 , 10 ) ; i ++ ) { let ct = 0 ; for ( let x = 0 ; x < path . length ; x ++ ) { if ( path [ x ] % prime [ i ] == 0 ) ct ++ ; } if ( ct > 1 ) { return false ; } } return true ; } function printCoPrimePaths ( path ) { for ( let x = 0 ; x < path . length ; x ++ ) { document . write ( path [ x ] + " " ) ; } document . write ( " " ) ; } function findCo_PrimePaths ( root , path ) { if ( root == null ) return ; path . push ( root . key ) ; findCo_PrimePaths ( root . left , path ) ; findCo_PrimePaths ( root . right , path ) ; if ( root . left == null && root . right == null ) { if ( isPathCo_Prime ( path ) ) { printCoPrimePaths ( path ) ; } } path . pop ( ) ; } function printCo_PrimePaths ( node ) { SieveOfEratosthenes ( ) ; let path = [ ] ; findCo_PrimePaths ( node , path ) ; } let root = newNode ( 10 ) ; root . left = newNode ( 48 ) ; root . right = newNode ( 3 ) ; root . right . left = newNode ( 11 ) ; root . right . right = newNode ( 37 ) ; root . right . left . left = newNode ( 7 ) ; root . right . left . right = newNode ( 29 ) ; root . right . right . left = newNode ( 42 ) ; root . right . right . right = newNode ( 19 ) ; root . right . right . right . left = newNode ( 7 ) ; printCo_PrimePaths ( root ) ;