Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Problem Statement
Approach and Explanation
Java Implementation
Frequently Asked Questions
What do you mean by all prime levels?
What is a Queue?
Last Updated: Mar 27, 2024

Print all Prime Levels of a Binary Tree

Crack Google SDE interview : Essential projects
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM


This article discusses how to print all prime levels of a binary tree. A Binary Tree is a special tree data structure where each node has two child nodes only. Such problems may be asked in the coding interviews of many tech companies. Reading this article will surely help you better understand the concepts of Binary Trees and Tree Traversal.

In the given problem, we will perform a level order traversal, and check if all the elements of a level are prime or not. If all the elements are prime, we will print the whole level.

Also see, Data Structure

Problem Statement

Given a Binary Tree, print all the prime levels of the tree. That is, print those levels which have all prime numbers as nodes. 


Let us consider this Binary Tree.





7 11 

31 23 41 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job

Approach and Explanation

After seeing the above example, it must be clear what we are supposed to do. To clarify the problem again, we will first perform Level Order traversal, then check the nodes for prime; if prime, print that level. In this article, the implementation is done in Java.

To perform the required tasks, the step-by-step approach is as follows:

  • Since we are dealing with Binary Tree, we will create it by ourselves. So, we create a constructor TreeNode, with three members- data(int), left(TreeNode), and right(TreeNode).
  • Inside the constructor, we take the data of the node and store it. We also initialize the left and right pointers to null. 
  • We declare a function that takes the user-inputted binary tree and performs a level-order traversal. The level order traversal is saved in a queue. Let us call this function printPrimeTreeLevels(). From this function, we will call another function, say calcPrimeLvl().
  • In calcPrimeLvl(), we pass the queue, the start index, and the size. 
    • This function is responsible for getting the prime level of the given Binary Tree. We check if the root is prime or not using checkPrime() function. 
    • We traverse one by one to check if the elements of the level are prime or not.
    • To ensure the given level is all prime or not, call the checkPrimeLevel() function and pass the queue, the start index, and the size.
    • If the level is all prime, we print that level by calling the printTreeLevels() function.
  • The helper function checkPrime() simply checks if the incoming number is prime or not. It returns true or false depending on the number.
  • The helper function checkPrimeLevel() does the same. It calls the function checkPrime() for each of the queue elements and returns true if all the elements of the same level are prime or not.
  • The function printTreeLevels() takes the queue, the start index, and the size of the queue as the function arguments. It simply prints all the queue elements using a loop.
  • We also have a helper function called calcSize() that takes the binary tree as input and returns the size of the tree. Here size means the number of nodes.

Recommended: Before proceeding to the solution code, try to solve the problem on your own first. 

Java Implementation

public class PrintPrimeLevels {

  static class TreeNode{

      public int data;
      public TreeNode left,right;

      public TreeNode(int data){
 = data;
          left = right = null;

  static TreeNode addNode(int data){
      TreeNode tmp = new TreeNode(data);
      return tmp;

  static boolean checkPrime(int num){
      if(num == 1){
          return false;

      for(int i=2; i*i <= num; i++){
          if(num % i == 0){
              return false;

      return true;

  static void printTreeLevels(TreeNode[] q, int idx, int size){

      for(int i=idx; i < size; i++){
          System.out.print(q[i].data + " ");

  static boolean checkPrimeLevel(TreeNode[] q, int idx, int size){

      for(int i=idx; i< size; i++){
              return false;

      return true;

  static void calcPrimeLvl(TreeNode[] q, int idx, int size){

      while(idx < size){
          int currentSize = size;

          while(idx < currentSize){
              TreeNode tmp = q[idx];

              if(tmp.left != null){
                  q[size++] = tmp.left;

              if(tmp.right != null){
                  q[size++] = tmp.right;


          if(checkPrimeLevel(q, idx, size-1)){
              printTreeLevels(q, idx, size);

  static int calcSize(TreeNode tn){
      if(tn == null){
          return 0;

      return 1 + calcSize(tn.left) + calcSize(tn.right);

  static void printPrimeTreeLevels(TreeNode tn){

      int treeSize = calcSize(tn);

      TreeNode[] q = new TreeNode[treeSize];

      for(int i = 0; i<treeSize; i++){
          q[i] = new TreeNode(0);
          q[0] = tn;

      calcPrimeLvl(q, 0, 1);

  public static void main(String[] args) {

      Input Binary Tree
                /     \
              7        11
            /    \     /   \
          13     10   17    19
        /          \          \
      31            19         41


      TreeNode root = addNode(5);
      root.left = addNode(7);
      root.right = addNode(11);

      root.left.left = addNode(13);
      root.left.right = addNode(10);

      root.right.left = addNode(17);
      root.right.right = addNode(19);

      root.left.left.left = addNode(31);
      root.left.right.right = addNode(23);
      root.right.right.right = addNode(41);



7 11 
31 23 41 


Time Complexity

In the given implementation, we traverse each node of the Binary Tree to check whether it is prime or not. Thus, the time complexity is, T(n) = O(N), where N is the size of the Binary Tree.

Space Complexity

In the given implementation, we maintain a queue that contains all the nodes in level order. Thus, Space Complexity = O(N), where N is the size of the Binary Tree.

Frequently Asked Questions

What do you mean by all prime levels?

In a tree, if all the nodes of a level are prime, then that level is called all prime levels. A prime number is a number that is divisible by 1 and itself only.

What is a Queue?

A queue is a linear data structure that follows the FIFO (First In First Out) sequence. To learn more about queues, click here Queue. 


To summarize our article, we discussed the print of all prime levels of a binary tree problem. We first saw the problem statement, an example, and an approach. We also saw the Java implementation of our approach along with the time and space complexity. We summed up the article with a few FAQs.

Improve your coding skills by practicing various problems of various difficulty levels on our Coding Ninjas Studio.

Learn about various topics like Web Technologies, Programming Fundamentals, Aptitude, DSA, and much more from our CN Library | Free Online Coding Resources.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Previous article
Sum of all numbers that are formed from root to leaf paths
Next article
Exponential Levels of a Binary Tree
Live masterclass