Print the nodes of the Binary Tree whose height is a Prime number | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100000 NEW_LINE vector < int > graph [ MAX + 1 ] ; vector < bool > Prime ( MAX + 1 , true ) ; int height [ MAX + 1 ] ; 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 ; } } } } 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 ) ; } } void primeHeightNode ( int N ) { SieveOfEratosthenes ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { if ( Prime [ height [ i ] ] ) { cout << i << " ▁ " ; } } } int main ( ) { int N = 5 ; graph [ 1 ] . push_back ( 2 ) ; graph [ 1 ] . push_back ( 3 ) ; graph [ 2 ] . push_back ( 4 ) ; graph [ 2 ] . push_back ( 5 ) ; dfs ( 1 , 1 , 0 ) ; primeHeightNode ( N ) ; return 0 ; }