Print the nodes of the Binary Tree whose height is a Prime number | Java 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
import java . util . * ; class GFG { static final int MAX = 100000 ; @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] graph = new Vector [ MAX + 1 ] ; static boolean [ ] Prime = new boolean [ MAX + 1 ] ; static int [ ] height = new int [ MAX + 1 ] ; static void SieveOfEratosthenes ( ) { int i , j ; Prime [ 0 ] = Prime [ 1 ] = false ; for ( i = 2 ; i * i <= MAX ; i ++ ) { if ( Prime [ i ] ) { for ( j = 2 * i ; j < MAX ; j += i ) { Prime [ j ] = false ; } } } } static void dfs ( int node , int parent , int h ) { height [ node ] = h ; for ( int to : graph [ node ] ) { if ( to == parent ) continue ; dfs ( to , node , h + 1 ) ; } } static void primeHeightNode ( int N ) { SieveOfEratosthenes ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { if ( Prime [ height [ i ] ] ) { System . out . print ( i + " ▁ " ) ; } } } public static void main ( String [ ] args ) { int N = 5 ; for ( int i = 0 ; i < Prime . length ; i ++ ) Prime [ i ] = true ; for ( int i = 0 ; i < graph . length ; i ++ ) graph [ i ] = new Vector < Integer > ( ) ; graph [ 1 ] . add ( 2 ) ; graph [ 1 ] . add ( 3 ) ; graph [ 2 ] . add ( 4 ) ; graph [ 2 ] . add ( 5 ) ; dfs ( 1 , 1 , 0 ) ; primeHeightNode ( N ) ; } }