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 ; Driver code ; Create Binary Tree as shown ; Print Co - Prime Paths
class Node : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . key = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( key ) : NEW_LINE INDENT temp = Node ( key ) NEW_LINE return temp NEW_LINE DEDENT N = 1000000 NEW_LINE prime = [ ] NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT check = [ True for i in range ( N + 1 ) ] NEW_LINE p = 2 NEW_LINE while ( p * p <= N ) : NEW_LINE INDENT if ( check [ p ] ) : NEW_LINE INDENT prime . append ( p ) NEW_LINE for i in range ( p * p , N + 1 , p ) : NEW_LINE INDENT check [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def isPathCo_Prime ( path ) : NEW_LINE INDENT max = 0 NEW_LINE for x in path : NEW_LINE INDENT if ( max < x ) : NEW_LINE INDENT max = x NEW_LINE DEDENT DEDENT i = 0 NEW_LINE while ( i * prime [ i ] <= max // 2 ) : NEW_LINE INDENT ct = 0 NEW_LINE for x in path : NEW_LINE INDENT if ( x % prime [ i ] == 0 ) : NEW_LINE INDENT ct += 1 NEW_LINE DEDENT DEDENT if ( ct > 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return True NEW_LINE DEDENT def printCo_PrimePaths ( path ) : NEW_LINE INDENT for x in path : NEW_LINE INDENT print ( x , end = ' ▁ ' ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT def findCo_PrimePaths ( root , path ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return path NEW_LINE DEDENT path . append ( root . key ) NEW_LINE path = findCo_PrimePaths ( root . left , path ) NEW_LINE path = findCo_PrimePaths ( root . right , path ) NEW_LINE if ( root . left == None and root . right == None ) : NEW_LINE INDENT if ( isPathCo_Prime ( path ) ) : NEW_LINE INDENT printCo_PrimePaths ( path ) NEW_LINE DEDENT DEDENT path . pop ( ) NEW_LINE return path NEW_LINE DEDENT def printCo_PrimePath ( node ) : NEW_LINE INDENT SieveOfEratosthenes ( ) NEW_LINE path = [ ] NEW_LINE path = findCo_PrimePaths ( node , path ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = newNode ( 10 ) NEW_LINE root . left = newNode ( 48 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . right . left = newNode ( 11 ) NEW_LINE root . right . right = newNode ( 37 ) NEW_LINE root . right . left . left = newNode ( 7 ) NEW_LINE root . right . left . right = newNode ( 29 ) NEW_LINE root . right . right . left = newNode ( 42 ) NEW_LINE root . right . right . right = newNode ( 19 ) NEW_LINE root . right . right . right . left = newNode ( 7 ) NEW_LINE printCo_PrimePath ( root ) NEW_LINE DEDENT