Print the nodes of the Binary Tree whose height is a Prime number | Python3 implementation of nodes at prime height in the given tree ; To store Prime Numbers ; To store height of each node ; Function to find the prime numbers till 10 ^ 5 ; Traverse all multiple of i and make it false ; Function to perform dfs ; Store the height of node ; Function to find the nodes at prime height ; To precompute prime number till 10 ^ 5 ; Check if height [ node ] is prime ; Driver code ; Number of nodes ; Edges of the tree
MAX = 100000 NEW_LINE graph = [ [ ] for i in range ( MAX + 1 ) ] NEW_LINE Prime = [ True for i in range ( MAX + 1 ) ] NEW_LINE height = [ 0 for i in range ( MAX + 1 ) ] NEW_LINE def SieveOfEratosthenes ( ) : NEW_LINE INDENT Prime [ 0 ] = Prime [ 1 ] = False NEW_LINE i = 2 NEW_LINE while i * i <= MAX : NEW_LINE INDENT if ( Prime [ i ] ) : NEW_LINE INDENT for j in range ( 2 * i , MAX , i ) : NEW_LINE INDENT Prime [ j ] = False NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def dfs ( node , parent , h ) : NEW_LINE INDENT height [ node ] = h NEW_LINE for to in graph [ node ] : NEW_LINE INDENT if ( to == parent ) : NEW_LINE INDENT continue NEW_LINE DEDENT dfs ( to , node , h + 1 ) NEW_LINE DEDENT DEDENT def primeHeightNode ( N ) : NEW_LINE INDENT SieveOfEratosthenes ( ) NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( Prime [ height [ i ] ] ) : NEW_LINE INDENT print ( i , end = ' ▁ ' ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 5 NEW_LINE graph [ 1 ] . append ( 2 ) NEW_LINE graph [ 1 ] . append ( 3 ) NEW_LINE graph [ 2 ] . append ( 4 ) NEW_LINE graph [ 2 ] . append ( 5 ) NEW_LINE dfs ( 1 , 1 , 0 ) NEW_LINE primeHeightNode ( N ) NEW_LINE DEDENT