Given a Binary Tree, the task is to print all prime levels of this tree.
Any level of a Binary tree is said to be a prime level, if all nodes of this level are prime.
Examples:
Input:
1
/ \
15 13
/ / \
11 7 29
\ /
2 3
Output: 11 7 29
2 3
Explanation:
Third and Fourth levels are prime levels.
Input:
7
/ \
23 41
/ \ \
31 16 3
/ \ \ /
2 5 17 11
/
23
Output: 7
23 41
2 5 17 11
23
Explanation:
First, Second, Fourth and
Fifth levels are prime levels.
Approach: In order to check if a level is Prime level or not,
- We first need to make a level order traversal of the binary tree to get the node values of each level.
- Here a Queue data structure is used to store the levels of the tree while doing the level order traversal.
- Then for each level, check if it is a prime level or not.
Below is the implementation of the above approach:
C++
// C++ program for printing a prime// levels of binary Tree#include <bits/stdc++.h>using namespace std;// A Tree nodestruct Node { int key; struct Node *left, *right;};// Utility function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Function to check whether node// Value is prime or notbool isPrime(int n){ if (n == 1) return false; // Iterate from 2 to sqrt(n) for (int i = 2; i * i <= n; i++) { // If it has a factor if (n % i == 0) { return false; } } return true;}// Function to print a Prime levelvoid printLevel(struct Node* queue[], int index, int size){ for (int i = index; i < size; i++) { cout << queue[i]->key << " "; } cout << endl;}// Function to check whether given level is// prime level or notbool isLevelPrime(struct Node* queue[], int index, int size){ for (int i = index; i < size; i++) { // Check value of node is // pPrime or not if (!isPrime(queue[index++]->key)) { return false; } } // Return true if for loop // iIterate completely return true;}// Utility function to get Prime// Level of a given Binary treevoid findPrimeLevels(struct Node* node, struct Node* queue[], int index, int size){ // Print root node value, if Prime if (isPrime(queue[index]->key)) { cout << queue[index]->key << endl; } // Run while loop while (index < size) { int curr_size = size; // Run inner while loop while (index < curr_size) { struct Node* temp = queue[index]; // Push left child in a queue if (temp->left != NULL) queue[size++] = temp->left; // Push right child in a queue if (temp->right != NULL) queue[size++] = temp->right; // Increment index index++; } // If condition to check, level is // prime or not if (isLevelPrime( queue, index, size - 1)) { // Function call to print // prime level printLevel(queue, index, size); } }}// Function to find total no of nodes// In a given binary treeint findSize(struct Node* node){ // Base condition if (node == NULL) return 0; return 1 + findSize(node->left) + findSize(node->right);}// Function to find Prime levels// In a given binary treevoid printPrimeLevels(struct Node* node){ int t_size = findSize(node); // Create queue struct Node* queue[t_size]; // Push root node in a queue queue[0] = node; // Function call findPrimeLevels(node, queue, 0, 1);}// Driver Codeint main(){ /* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */ // Create Binary Tree as shown Node* root = newNode(10); root->left = newNode(13); root->right = newNode(11); root->right->left = newNode(19); root->right->right = newNode(23); root->right->left->left = newNode(21); root->right->left->right = newNode(29); root->right->right->left = newNode(43); root->right->right->right = newNode(15); root->right->right->right->left = newNode(7); // Print Prime Levels printPrimeLevels(root); return 0;} |
Java
// Java program for the above approachpublic class Main{ // A Tree node static class Node { public int key; public Node left, right; public Node(int key) { this.key = key; left = right = null; } } // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(key); return temp; } // Function to check whether node // Value is prime or not static boolean isPrime(int n) { if (n == 1) return false; // Iterate from 2 to sqrt(n) for(int i = 2; i * i <= n; i++) { // If it has a factor if (n % i == 0) { return false; } } return true; } // Function to print a Prime level static void printLevel(Node[] queue, int index, int size) { for(int i = index; i < size; i++) { System.out.print(queue[i].key + " "); } System.out.println(); } // Function to check whether given level is // prime level or not static boolean isLevelPrime(Node[] queue, int index, int size) { for(int i = index; i < size; i++) { // Check value of node is // pPrime or not if (!isPrime(queue[index++].key)) { return false; } } // Return true if for loop // iIterate completely return true; } // Utility function to get Prime // Level of a given Binary tree static void findPrimeLevels(Node node, Node[] queue, int index, int size) { // Print root node value, if Prime if (isPrime(queue[index].key)) { System.out.println(queue[index].key); } // Run while loop while (index < size) { int curr_size = size; // Run inner while loop while (index < curr_size) { Node temp = queue[index]; // Push left child in a queue if (temp.left != null) queue[size++] = temp.left; // Push right child in a queue if (temp.right != null) queue[size++] = temp.right; // Increment index index++; } // If condition to check, level is // prime or not if (isLevelPrime(queue, index, size - 1)) { // Function call to print // prime level printLevel(queue, index, size); } } } // Function to find total no of nodes // In a given binary tree static int findSize(Node node) { // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right); } // Function to find Prime levels // In a given binary tree static void printPrimeLevels(Node node) { int t_size = findSize(node); // Create queue Node[] queue = new Node[t_size]; for(int i = 0; i < t_size; i++) { queue[i] = new Node(0); } // Push root node in a queue queue[0] = node; // Function call findPrimeLevels(node, queue, 0, 1); } public static void main(String[] args) { /* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); // Print Prime Levels printPrimeLevels(root); }}// This code is contributed by suresh07. |
Python3
# Python3 program for printing a prime# levels of binary Tree # A Tree nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None # function to create a # new nodedef newNode(key): temp = Node(key); return temp; # Function to check whether # node Value is prime or notdef isPrime(n): if (n == 1): return False; i = 2 # Iterate from 2 # to sqrt(n) while(i * i <= n): # If it has a factor if (n % i == 0): return False; i += 1 return True;# Function to print a # Prime leveldef printLevel(queue, index, size): for i in range(index, size): print(queue[i].key, end = ' ') print() # Function to check whether # given level is prime level # or notdef isLevelPrime(queue, index, size): for i in range(index, size): # Check value of node is # pPrime or not if (not isPrime(queue[index].key)): index += 1 return False; # Return true if for loop # iIterate completely return True; # Utility function to get Prime# Level of a given Binary treedef findPrimeLevels(node, queue, index, size): # Print root node value, if Prime if (isPrime(queue[index].key)): print(queue[index].key) # Run while loop while (index < size): curr_size = size; # Run inner while loop while (index < curr_size): temp = queue[index]; # Push left child in a queue if (temp.left != None): queue[size] = temp.left; size+=1 # Push right child in a queue if (temp.right != None): queue[size] = temp.right; size+=1 # Increment index index+=1; # If condition to check, level # is prime or not if (isLevelPrime(queue, index, size - 1)): # Function call to print # prime level printLevel(queue, index, size); # Function to find total no # of nodes In a given binary# treedef findSize(node): # Base condition if (node == None): return 0; return (1 + findSize(node.left) + findSize(node.right)); # Function to find Prime levels# In a given binary treedef printPrimeLevels(node): t_size = findSize(node); # Create queue queue=[0 for i in range(t_size)] # Push root node in a queue queue[0] = node; # Function call findPrimeLevels(node, queue, 0, 1); # Driver code if __name__ == "__main__": ''' 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 ''' # Create Binary Tree as shown root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); # Print Prime Levels printPrimeLevels(root);# This code is contributed by Rutvik_56 |
C#
// C# program for printing a prime// levels of binary Treeusing System;using System.Collections.Generic;class GFG { // A Tree node class Node { public int key; public Node left, right; public Node(int key) { this.key = key; left = right = null; } } // Utility function to create a new node static Node newNode(int key) { Node temp = new Node(key); return temp; } // Function to check whether node // Value is prime or not static bool isPrime(int n) { if (n == 1) return false; // Iterate from 2 to sqrt(n) for(int i = 2; i * i <= n; i++) { // If it has a factor if (n % i == 0) { return false; } } return true; } // Function to print a Prime level static void printLevel(Node[] queue, int index, int size) { for(int i = index; i < size; i++) { Console.Write(queue[i].key + " "); } Console.WriteLine(); } // Function to check whether given level is // prime level or not static bool isLevelPrime(Node[] queue, int index, int size) { for(int i = index; i < size; i++) { // Check value of node is // pPrime or not if (!isPrime(queue[index++].key)) { return false; } } // Return true if for loop // iIterate completely return true; } // Utility function to get Prime // Level of a given Binary tree static void findPrimeLevels(Node node, Node[] queue, int index, int size) { // Print root node value, if Prime if (isPrime(queue[index].key)) { Console.WriteLine(queue[index].key); } // Run while loop while (index < size) { int curr_size = size; // Run inner while loop while (index < curr_size) { Node temp = queue[index]; // Push left child in a queue if (temp.left != null) queue[size++] = temp.left; // Push right child in a queue if (temp.right != null) queue[size++] = temp.right; // Increment index index++; } // If condition to check, level is // prime or not if (isLevelPrime(queue, index, size - 1)) { // Function call to print // prime level printLevel(queue, index, size); } } } // Function to find total no of nodes // In a given binary tree static int findSize(Node node) { // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right); } // Function to find Prime levels // In a given binary tree static void printPrimeLevels(Node node) { int t_size = findSize(node); // Create queue Node[] queue = new Node[t_size]; for(int i = 0; i < t_size; i++) { queue[i] = new Node(0); } // Push root node in a queue queue[0] = node; // Function call findPrimeLevels(node, queue, 0, 1); } static void Main() { /* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */ // Create Binary Tree as shown Node root = newNode(10); root.left = newNode(13); root.right = newNode(11); root.right.left = newNode(19); root.right.right = newNode(23); root.right.left.left = newNode(21); root.right.left.right = newNode(29); root.right.right.left = newNode(43); root.right.right.right = newNode(15); root.right.right.right.left = newNode(7); // Print Prime Levels printPrimeLevels(root); }}// This code is contributed by mukesh07. |
Javascript
<script>// Javascript program for printing a// prime levels of binary Tree// A Tree nodeclass Node{ constructor(key) { this.left = null; this.right = null; this.key = key; }}// Utility function to create a new nodefunction newNode(key){ let temp = new Node(key); return (temp);}// Function to check whether node// Value is prime or notfunction isPrime(n){ if (n == 1) return false; // Iterate from 2 to sqrt(n) for(let i = 2; i * i <= n; i++) { // If it has a factor if (n % i == 0) { return false; } } return true;}// Function to print a Prime levelfunction printLevel(queue, index, size){ for(let i = index; i < size; i++) { document.write(queue[i].key + " "); } document.write("</br>");}// Function to check whether given level is// prime level or notfunction isLevelPrime(queue, index, size){ for(let i = index; i < size; i++) { // Check value of node is // pPrime or not if (!isPrime(queue[index++].key)) { return false; } } // Return true if for loop // iIterate completely return true;}// Utility function to get Prime// Level of a given Binary treefunction findPrimeLevels(node, queue, index, size){ // Print root node value, if Prime if (isPrime(queue[index].key)) { document.write(queue[index].key + "</br>"); } // Run while loop while (index < size) { let curr_size = size; // Run inner while loop while (index < curr_size) { let temp = queue[index]; // Push left child in a queue if (temp.left != null) queue[size++] = temp.left; // Push right child in a queue if (temp.right != null) queue[size++] = temp.right; // Increment index index++; } // If condition to check, level is // prime or not if (isLevelPrime(queue, index, size - 1)) { // Function call to print // prime level printLevel(queue, index, size); } }}// Function to find total no of nodes// In a given binary treefunction findSize(node){ // Base condition if (node == null) return 0; return 1 + findSize(node.left) + findSize(node.right);}// Function to find Prime levels// In a given binary treefunction printPrimeLevels(node){ let t_size = findSize(node); // Create queue let queue = new Array(t_size); for(let i = 0; i < t_size; i++) { queue[i] = new Node(); } // Push root node in a queue queue[0] = node; // Function call findPrimeLevels(node, queue, 0, 1);}// Driver code/* 10 / \ 13 11 / \ 19 23 / \ / \ 21 29 43 15 / 7 */// Create Binary Tree as shownlet root = newNode(10);root.left = newNode(13);root.right = newNode(11);root.right.left = newNode(19);root.right.right = newNode(23);root.right.left.left = newNode(21);root.right.left.right = newNode(29);root.right.right.left = newNode(43);root.right.right.right = newNode(15);root.right.right.right.left = newNode(7);// Print Prime LevelsprintPrimeLevels(root);// This code is contributed by mukesh07</script> |
Output:
13 11 19 23 7
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!