Breadth First Search
Approach Steps:
- uses a queue data structure to keep track of nodes at each level and checks each dequeued node for primality.
- If a node is prime and at the desired level, it is added to a list of prime numbers at that level.
- After all nodes at the current level have been processed, the list of prime numbers is printed in the desired format and variables are updated to process the next level.
- Last ensures that nodes at each level are processed before moving on to the next level.
- and the queue ensures that nodes are processed in the order in which they appear at each level.
Below is the code implementation:
C++
#include <cmath> #include <iostream> #include <queue> // Binary Tree node definition struct Node { int val; Node* left; Node* right; Node( int val = 0, Node* left = nullptr, Node* right = nullptr) : val(val) , left(left) , right(right) { } }; // Function to check if a number is prime bool is_prime( int num) { if (num < 2) { return false ; } for ( int i = 2; i <= std:: sqrt (num); i++) { if (num % i == 0) { return false ; } } return true ; } // Function to print all prime numbers at level k of a // binary tree void print_primes_at_level(Node* root, int k) { std::queue<Node*> q; q.push(root); int curr_level = 1; int curr_nodes = 1; int next_nodes = 0; std::vector< int > primes; // Loop until all levels have been traversed while (!q.empty()) { Node* node = q.front(); q.pop(); if (is_prime(node->val) && curr_level == k) { primes.push_back(node->val); } if (node->left) { q.push(node->left); next_nodes++; } if (node->right) { q.push(node->right); next_nodes++; } curr_nodes--; if (curr_nodes == 0) { if (!primes.empty()) { std::cout << "Primes at level " << k << ": " ; for ( int prime : primes) { std::cout << prime << " " ; } std::cout << std::endl; } primes.clear(); curr_level++; curr_nodes = next_nodes; next_nodes = 0; } if (curr_level > k) { break ; } } } // Example usage int main() { Node* root = new Node( 2, new Node(3, new Node(7), new Node(11)), new Node(5, new Node(13), new Node(17))); print_primes_at_level(root, 1); print_primes_at_level(root, 2); print_primes_at_level(root, 3); // Free allocated memory to avoid memory leak delete root->right->right; delete root->right->left; delete root->left->right; delete root->left->left; delete root->right; delete root->left; delete root; return 0; } |
Java
import java.util.*; // Binary Tree node definition class Node { int val; Node left; Node right; Node( int val) { this .val = val; left = null ; right = null ; } } public class GFG { // Function to check if a number is prime static boolean isPrime( int num) { if (num < 2 ) { return false ; } // Loop from 2 to the square root of num to check for divisibility for ( int i = 2 ; i <= Math.sqrt(num); i++) { if (num % i == 0 ) { return false ; } } return true ; } // Function to print all prime numbers at level k of a binary tree static void printPrimesAtLevel(Node root, int k) { Queue<Node> q = new LinkedList<>(); q.add(root); int currLevel = 1 ; int currNodes = 1 ; int nextNodes = 0 ; List<Integer> primes = new ArrayList<>(); // Loop until all levels have been traversed while (!q.isEmpty()) { Node node = q.poll(); if (isPrime(node.val) && currLevel == k) { primes.add(node.val); } if (node.left != null ) { q.add(node.left); nextNodes++; } if (node.right != null ) { q.add(node.right); nextNodes++; } currNodes--; if (currNodes == 0 ) { if (!primes.isEmpty()) { System.out.print( "Primes at level " + k + ": " ); for ( int prime : primes) { System.out.print(prime + " " ); } System.out.println(); } primes.clear(); currLevel++; currNodes = nextNodes; nextNodes = 0 ; } if (currLevel > k) { break ; } } } // Example usage public static void main(String[] args) { Node root = new Node( 2 ); root.left = new Node( 3 ); root.right = new Node( 5 ); root.left.left = new Node( 7 ); root.left.right = new Node( 11 ); root.right.left = new Node( 13 ); root.right.right = new Node( 17 ); printPrimesAtLevel(root, 1 ); printPrimesAtLevel(root, 2 ); printPrimesAtLevel(root, 3 ); } } |
Python
import math from Queue import Queue # Binary Tree node definition class Node: def __init__( self , val = None , left = None , right = None ): self .val = val self .left = left self .right = right # Function to print all prime numbers at level k of a binary tree def print_primes_at_level(root, k): q = Queue() q.put(root) curr_level = 1 curr_nodes = 1 next_nodes = 0 primes = [] # Loop until all levels have been traversed while not q.empty(): node = q.get() if is_prime(node.val) and curr_level = = k: primes.append(node.val) if node.left: q.put(node.left) next_nodes + = 1 if node.right: q.put(node.right) next_nodes + = 1 curr_nodes - = 1 if curr_nodes = = 0 : if primes: print ( "primes at level {}: {}" . format (k, ' ' .join( str (p) for p in primes))) primes = [] curr_level + = 1 curr_nodes = next_nodes next_nodes = 0 if curr_level > k: break # Function to check if a number is prime def is_prime(num): if num < 2 : return False for i in range ( 2 , int (math.sqrt(num)) + 1 ): if num % i = = 0 : return False return True # Example usage root = Node( 2 , Node( 3 , Node( 7 ), Node( 11 )), Node( 5 , Node( 13 ), Node( 17 ))) print_primes_at_level(root, 1 ) print_primes_at_level(root, 2 ) print_primes_at_level(root, 3 ) |
C#
using System; using System.Collections.Generic; // Binary Tree node definition class Node { public int val; public Node left; public Node right; public Node( int val = 0, Node left = null , Node right = null ) { this .val = val; this .left = left; this .right = right; } } // Function to print all prime numbers at level k of a binary tree class GFG { static void PrintPrimesAtLevel(Node root, int k) { Queue<Node> queue = new Queue<Node>(); queue.Enqueue(root); int currLevel = 1; int currNodes = 1; int nextNodes = 0; List< int > primes = new List< int >(); // Loop until all levels have been traversed while (queue.Count > 0) { Node node = queue.Dequeue(); if (IsPrime(node.val) && currLevel == k) { primes.Add(node.val); } if (node.left != null ) { queue.Enqueue(node.left); nextNodes++; } if (node.right != null ) { queue.Enqueue(node.right); nextNodes++; } currNodes--; if (currNodes == 0) { if (primes.Count > 0) { Console.WriteLine($ "Primes at level {k}: {string.Join(" ", primes)}" ); } primes.Clear(); currLevel++; currNodes = nextNodes; nextNodes = 0; } if (currLevel > k) { break ; } } } // Function to check if a number is prime static bool IsPrime( int num) { if (num < 2) { return false ; } for ( int i = 2; i <= Math.Sqrt(num); i++) { if (num % i == 0) { return false ; } } return true ; } // Example usage static void Main() { Node root = new Node(2, new Node(3, new Node(7), new Node(11)), new Node(5, new Node(13), new Node(17))); PrintPrimesAtLevel(root, 1); PrintPrimesAtLevel(root, 2); PrintPrimesAtLevel(root, 3); } } |
Javascript
// Binary Tree node definition class Node { constructor(val = 0, left = null , right = null ) { this .val = val; this .left = left; this .right = right; } } // Function to check if a number is prime function isPrime(num) { if (num < 2) { return false ; } for (let i = 2; i <= Math.sqrt(num); i++) { if (num % i === 0) { return false ; } } return true ; } // Function to print all prime numbers at level k of a binary tree function printPrimesAtLevel(root, k) { const queue = [root]; let currLevel = 1; let currNodes = 1; let nextNodes = 0; const primes = []; // Loop until all levels have been traversed while (queue.length > 0) { const node = queue.shift(); if (isPrime(node.val) && currLevel === k) { primes.push(node.val); } if (node.left) { queue.push(node.left); nextNodes++; } if (node.right) { queue.push(node.right); nextNodes++; } currNodes--; if (currNodes === 0) { if (primes.length > 0) { console.log(`Primes at level ${k}: ${primes.join( ' ' )}`); } primes.length = 0; currLevel++; currNodes = nextNodes; nextNodes = 0; } if (currLevel > k) { break ; } } } // Example usage const root = new Node( 2, new Node(3, new Node(7), new Node(11)), new Node(5, new Node(13), new Node(17))); printPrimesAtLevel(root, 1); printPrimesAtLevel(root, 2); printPrimesAtLevel(root, 3); |
primes at level 1: 2 primes at level 2: 3 5 primes at level 3: 7 11 13 17
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Auxiliary Space: O(m), where m is the maximum number of nodes at a single level in the binary tree.
Prime Numbers present at Kth level of a Binary Tree
Given a number K, the task is to print the prime numbers present at that level given all the prime numbers are represented in the form of a binary tree.
Examples:
Input: K = 3
2
/ \
3 5
/\ / \
7 11 13 17
Output :7, 11, 13, 17
Explanation:
2
/ \
3 5
/\ / \
7 11 13 17
So primes present at level 3 : 7, 11, 13, 17
Input :K = 2
2
/ \
3 5
Output :3 5
Naive Approach: The naive approach is to build a binary tree of prime numbers and then get elements at a particular level k.
It doesn’t work well for large numbers as it takes too much time.
Efficient approach: Suppose there are n elements and the task is to build a binary tree using those n elements, then they can be built using log2n levels.
Therefore, given a level k, elements present here is from 2k-1 to 2k-1 if all the prime numbers are present in a 1D array.
Hence, the following is the algorithm:
- Find the prime numbers upto MAX_SIZE using Sieve of Eratosthenes.
- Calculate the left_index and right_index of the level as left_index = 2k-1, right_index = 2k-1.
- Output primes from left_index to right_index of prime array.
C++
// CPP program of the approach #include <bits/stdc++.h> using namespace std; // initializing the max value #define MAX_SIZE 1000005 // To store all prime numbers vector< int > primes; // Function to generate N prime numbers using // Sieve of Eratosthenes void SieveOfEratosthenes(vector< int >& primes) { // Create a boolean array "IsPrime[0..MAX_SIZE]" and // initialize all entries it as true. A value in // IsPrime[i] will finally be false if i is // Not a IsPrime, else true. bool IsPrime[MAX_SIZE]; memset (IsPrime, true , sizeof (IsPrime)); for ( int p = 2; p * p < MAX_SIZE; p++) { // If IsPrime[p] is not changed, then it is a prime if (IsPrime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX_SIZE; i += p) IsPrime[i] = false ; } } // Store all prime numbers for ( int p = 2; p < MAX_SIZE; p++) if (IsPrime[p]) primes.push_back(p); } void printLevel( int level) { cout << "primes at level " << level << ": " ; int left_index = pow (2, level - 1); int right_index = pow (2, level) - 1; for ( int i = left_index; i <= right_index; i++) { cout << primes[i - 1] << " " ; } cout << endl; } // Driver Code int main() { // Function call SieveOfEratosthenes(primes); printLevel(1); printLevel(2); printLevel(3); printLevel(4); return 0; } |
Java
// Java program of the approach import java.util.*; class GFG { // initializing the max value static final int MAX_SIZE = 1000005 ; // To store all prime numbers static Vector<Integer> primes = new Vector<Integer>(); // Function to generate N prime numbers using // Sieve of Eratosthenes static void SieveOfEratosthenes(Vector<Integer> primes) { // Create a boolean array "IsPrime[0..MAX_SIZE]" and // initialize all entries it as true. A value in // IsPrime[i] will finally be false if i is // Not a IsPrime, else true. boolean [] IsPrime = new boolean [MAX_SIZE]; for ( int i = 0 ; i < MAX_SIZE; i++) IsPrime[i] = true ; for ( int p = 2 ; p * p < MAX_SIZE; p++) { // If IsPrime[p] is not changed, then it is a prime if (IsPrime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX_SIZE; i += p) IsPrime[i] = false ; } } // Store all prime numbers for ( int p = 2 ; p < MAX_SIZE; p++) if (IsPrime[p]) primes.add(p); } static void printLevel( int level) { System.out.print( "primes at level " + level + ": " ); int left_index = ( int ) Math.pow( 2 , level - 1 ); int right_index = ( int ) (Math.pow( 2 , level) - 1 ); for ( int i = left_index; i <= right_index; i++) { System.out.print(primes.get(i - 1 ) + " " ); } System.out.println(); } // Driver Code public static void main(String[] args) { // Function call SieveOfEratosthenes(primes); printLevel( 1 ); printLevel( 2 ); printLevel( 3 ); printLevel( 4 ); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program of the approach MAX_SIZE = 1000005 primes = [] # Function to generate N prime numbers using # Sieve of Eratosthenes def SieveOfEratosthenes(): # Create a boolean array "IsPrime[0..MAX_SIZE]" and # initialize all entries it as True. A value in # IsPrime[i] will finally be false if i is # Not a IsPrime, else True. IsPrime = [ True ] * MAX_SIZE p = 2 while p * p < MAX_SIZE: # If IsPrime[p] is not changed, then it is a prime if (IsPrime[p] = = True ): # Update all multiples of p greater than or # equal to the square of it # numbers which are multiple of p and are # less than p^2 are already been marked. for i in range (p * p, MAX_SIZE, p): IsPrime[i] = False p + = 1 # Store all prime numbers for p in range ( 2 , MAX_SIZE): if (IsPrime[p]): primes.append(p) def printLevel(level): print ( "primes at level " , level, ":" , end = " " ) left_index = pow ( 2 , level - 1 ) right_index = pow ( 2 , level) - 1 for i in range (left_index, right_index + 1 ): print (primes[i - 1 ], end = " " ) print () # Driver Code # Function call SieveOfEratosthenes() printLevel( 1 ) printLevel( 2 ) printLevel( 3 ) printLevel( 4 ) # This code is contributed by mohit kumar 29 |
C#
// C# program of the approach using System; using System.Collections.Generic; class GFG { // initializing the max value static readonly int MAX_SIZE = 1000005; // To store all prime numbers static List< int > primes = new List< int >(); // Function to generate N prime numbers using // Sieve of Eratosthenes static void SieveOfEratosthenes(List< int > primes) { // Create a bool array "IsPrime[0..MAX_SIZE]" and // initialize all entries it as true. A value in // IsPrime[i] will finally be false if i is // Not a IsPrime, else true. bool [] IsPrime = new bool [MAX_SIZE]; for ( int i = 0; i < MAX_SIZE; i++) IsPrime[i] = true ; for ( int p = 2; p * p < MAX_SIZE; p++) { // If IsPrime[p] is not changed, then it is a prime if (IsPrime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ( int i = p * p; i < MAX_SIZE; i += p) IsPrime[i] = false ; } } // Store all prime numbers for ( int p = 2; p < MAX_SIZE; p++) if (IsPrime[p]) primes.Add(p); } static void printLevel( int level) { Console.Write( "primes at level " + level + ": " ); int left_index = ( int ) Math.Pow(2, level - 1); int right_index = ( int ) (Math.Pow(2, level) - 1); for ( int i = left_index; i <= right_index; i++) { Console.Write(primes[i - 1] + " " ); } Console.WriteLine(); } // Driver Code public static void Main(String[] args) { // Function call SieveOfEratosthenes(primes); printLevel(1); printLevel(2); printLevel(3); printLevel(4); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program of the approach // Initializing the max value let MAX_SIZE = 1000005 // To store all prime numbers let primes = new Array(); // Function to generate N prime numbers using // Sieve of Eratosthenes function SieveOfEratosthenes(primes) { // Create a boolean array "IsPrime[0..MAX_SIZE]" and // initialize all entries it as true. A value in // IsPrime[i] will finally be false if i is // Not a IsPrime, else true. let IsPrime = new Array(MAX_SIZE).fill( true ); for (let p = 2; p * p < MAX_SIZE; p++) { // If IsPrime[p] is not changed, // then it is a prime if (IsPrime[p] == true ) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (let i = p * p; i < MAX_SIZE; i += p) IsPrime[i] = false ; } } // Store all prime numbers for (let p = 2; p < MAX_SIZE; p++) if (IsPrime[p]) primes.push(p); } function printLevel(level) { document.write( "primes at level " + level + ": " ); let left_index = Math.pow(2, level - 1); let right_index = Math.pow(2, level) - 1; for (let i = left_index; i <= right_index; i++) { document.write(primes[i - 1] + " " ); } document.write( "<br>" ); } // Driver Code // Function call SieveOfEratosthenes(primes); printLevel(1); printLevel(2); printLevel(3); printLevel(4); // This code is contributed by _saurabh_jaiswal </script> |
primes at level 1: 2 primes at level 2: 3 5 primes at level 3: 7 11 13 17 primes at level 4: 19 23 29 31 37 41 43 47