Data Modelling & AI Data Structure & Algorithm

Prime Numbers present at Kth level of a Binary Tree

23 June 2025

0

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 log₂n levels.
Therefore, given a level k, elements present here is from 2^k-1 to 2^k-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 = 2^k-1, right_index = 2^k-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>

Output

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

Approach: 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);

Output

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.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Prime Numbers present at Kth level of a Binary Tree

C++

Java

Python3

C#

Javascript

Approach: Breadth First Search

C++

Java

Python

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

Pixel phones on Android 16 QPR1 Beta 3.1 are experiencing Google Wallet errors

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

Google Home chief says he wants to earn back love and trust

UFS 5.0 is on the way, but most Android users probably won’t notice

EDITOR PICKS

Pixel phones on Android 16 QPR1 Beta 3.1 are experiencing Google Wallet errors

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

Google Home chief says he wants to earn back love and trust

POPULAR POSTS

Pixel phones on Android 16 QPR1 Beta 3.1 are experiencing Google Wallet errors

Google’s underrated AI shopping tool just made online shoe hunts surprisingly easy

Google Home chief says he wants to earn back love and trust

POPULAR CATEGORY

ABOUT US

FOLLOW US