Level order traversal of a Binary tree is one of the most frequently asked questions in coding interviews, But what happens when you modify this basic concept a bit? We get questions such as exponential levels of a binary tree in which we have to print only those levels which are exponential. Let’s understand the problem statement better below.
Understanding the Problem
We have been given a binary tree, and we have to print its level order traversal, but we only have to print those that are exponential.
But what are exponential levels?
An exponential level is a level in which all nodes of that level can be expressed in the form of X ^ Y, where ‘X’ is a minimum possible positive constant and ‘Y’ is a variable positive integer.
For example, consider this level.
81 3
Because 81, 3 can be expressed in the form of X ^ Y (3 ^ 4 and 3 ^ 1). Here, ‘X’ is 3, which is the same for the level, and ‘Y’ is 4 and 1 as this is variable.
Dry Run
Let’s see an example with a dry run so that the thing we have discussed will become more clear by the following example.
Now, if we print the level order traversal of the tree, we will get
1
2 3
16 2 8 4
According to the question, we only have to print those levels which can be expressed in the format of X ^ Y (As explained above).
Thus, our output will be.
1
16 2 8 4
As, 1 = 1 ^ 1
16 = 2 ^ 2 , 2 = 2 ^ 1, 8 = 2 ^ 3, 4 = 2 ^ 2.
Here ‘X’ = 2 (minimum positive integer, same for the level), and ‘Y’ is varied.
Approach
We’ll perform a level order traversal on the binary tree, and for every element on a particular level, we will check if it can be expressed in the form of X ^ Y, If any element can’t be expressed in the form of the X ^ Y then we will not print that particular level.
Now let's look at the code for better understanding.
Code
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
int N = 1e6;
// It will store all the prime nos.
vector<int> prime;
// A node of the Tree.
struct Node {
int key;
struct Node *left, *right;
};
// Sieve Of Eratosthenes function to store prime numbers in the 'PRIME' vector.
void SieveOfEratosthenes() {
bool check[N + 1];
memset(check, true, sizeof(check));
for (int p = 2; p * p <= N; p++) {
if (check[p] == true) {
prime.push_back(p);
for (int i = p*p; i <= N; i += p)
check[i] = false;
}
}
}
/* Function for the creation of a new node for the tree. */
Node* newNode(int key) {
Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return (temp);
}
bool is_key(int n, int x) {
double p;
p = log10(n) / log10(x);
int no = (int)(pow(x, int(p)));
if (n == no)
return true;
return false;
}
/* Function that will help in finding the x. */
int find_x(int n) {
if (n == 1)
return 1;
double num, den, p;
num = log10(n);
int x, no;
for (int i = 2; i <= n; i++) {
den = log10(i);
p = num / den;
no = (int)(pow(i, int(p)));
if (abs(no - n) < 1e-6) {
x = i;
break;
}
}
return x;
}
/* To check whether any given level is exponential or not. */
bool isLevelExponential(vector<int>& L) {
int x = find_x(L[0]);
for (int i = 1; i < L.size(); i++) {
if (!is_key(L[i], x))
return false;
}
return true;
}
/* Function will print the Exponential Level of a Binary tree. */
void printExponentialLevels(vector<int>& Lev) {
for (auto x : Lev) {
cout << x << " ";
}
cout << endl;
}
/* function to get Exponential Level of a Binary tree. */
void find_ExponentialLevels(struct Node* node, struct Node* queue[], int index, int size) {
vector<int> Lev;
while (index < size) {
int curr_size = size;
while (index < curr_size) {
struct Node* temp = queue[index];
Lev.push_back(temp->key);
if (temp->left != NULL)
queue[size++] = temp->left;
if (temp->right != NULL)
queue[size++] = temp->right;
index++;
}
if (isLevelExponential(Lev)) {
printExponentialLevels(Lev);
}
Lev.clear();
}
}
/* Function that will help in finding the total no of nodes in the binary tree. */
int findSize(struct Node* node) {
if (node == NULL)
return 0;
return 1
+ findSize(node->left)
+ findSize(node->right);
}
/* Function to print Exponential levels in the tree */
void printExponentialLevels(struct Node* node) {
int t_size = findSize(node);
struct Node* queue[t_size];
queue[0] = node;
find_ExponentialLevels(node, queue, 0, 1);
}
int main() {
// Creating a Binary Tree.
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(16);
root->left->right = newNode(2);
root->right->left = newNode(8);
root->right->right = newNode(4);
SieveOfEratosthenes();
cout << "The Exponential Levels of the Binary Tree are: " << endl;
printExponentialLevels(root);
return 0;
}
You can also try this code with Online C++ Compiler
import java.io.*;
import java.util.*;
class CodingNinjas {
static int N = (int)1e6;
static List<Integer> prime = new ArrayList<>();
// Sieve Of Eratosthenes function to store prime numbers.
static void SieveOfEratosthenes() {
boolean check[] = new boolean[N + 1];
for (int p=2; p*p <= N; p++)
{
if (check[p] == true) {
prime.add(p);
for (int i = p * p; i <= N; i += p) {
check[i] = false;
}
}
}
}
// A node of the Tree.
static class Node {
int key;
Node left, right;
}
/* Function for the creation of a new node for the tree. */
static Node newNode(int key) {
Node temp = new Node();
temp.key = key;
temp.left = temp.right = null;
return temp;
}
static boolean is_key(int n, int x) {
double p;
p = Math.log10(n) / Math.log10(x);
int no = (int)(Math.pow(x, (int)p));
if (n == no) {
return true;
}
return false;
}
static int find_x(int n)
{
if (n == 1) {
return 1;
}
double num, den, p;
num = Math.log10(n);
int x = 0;
int no;
for (int i = 2; i <= n; i++) {
den = Math.log10(i);
p = num / den;
no = (int)(Math.pow(i, (int)p));
if (Math.abs(no - n) < 1e-6) {
x = i;
break;
}
}
return x;
}
static boolean isLevelExponential(List<Integer> L)
{
int x = find_x(L.get(0));
for (int i = 1; i < L.size(); i++)
{
if (!is_key(L.get(i), x)) {
return false;
}
}
return true;
}
/* Function to print Exponential levels in the tree */
static void printExponentialLevels(List<Integer> Lev)
{
for (int i = 0; i < Lev.size(); i++) {
System.out.print(Lev.get(i) + " ");
}
System.out.println();
}
/* Function to find Exponential levels in the tree */
static void find_ExponentialLevels(Node node, List<Node> queue, iint index, int size)
{
List<Integer> Lev = new ArrayList<Integer>();
while (index < size) {
int curr_size = size;
while (index < curr_size) {
Node temp = queue.get(index);
Lev.add(temp.key);
if (temp.left != null) {
queue.add(size++, temp.left);
}
if (temp.right != null) {
queue.add(size++, temp.right);
}
index++;
}
if (isLevelExponential(Lev)) {
printExponentialLevels(Lev);
}
Lev.clear();
}
}
/* Method that will help in finding the total no of nodes in the binary tree. */
static int findSize(Node node)
{
if (node == null) {
return 0;
}
return 1 + findSize(node.left)
+ findSize(node.right);
}
static void printExponentialLevels(Node node)
{
int t_size = findSize(node);
List<Node> queue = new ArrayList<>(t_size);
queue.add(0, node);
find_ExponentialLevels(node, queue, 0, 1);
}
// The Main Function
public static void main(String[] args)
{
Node root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(16);
root.left.right = newNode(2);
root.right.left = newNode(8);
root.right.right = newNode(4);
SieveOfEratosthenes();
System.out.println("The Exponential Levels of the Binary Tree are:");
printExponentialLevels(root);
}
}
You can also try this code with Online Java Compiler
import math
# Node of the Binary Tree.
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# Method for the creation of a new node for the tree.
def newNode(key):
temp = Node(key)
return temp
N = 1000000
prime = []
# Sieve Of Eratosthenes method to store prime numbers.
def SieveOfEratosthenes():
check = [True for i in range(N + 1)]
p = 2
while(p * p <= N):
if (check[p]):
prime.append(p);
for i in range(p * p, N + 1, p):
check[i] = False;
p += 1
def is_key(n, x):
p = (math.log10(n) /
math.log10(x));
no = int(math.pow(x, int(p)));
if (n == no):
return True;
return False;
def find_x(n):
if (n == 1):
return 1;
den = 0
p = 0
num = math.log10(n);
x = 0
no = 0;
for i in range(2, n + 1):
den = math.log10(i);
p = num / den;
no = int(math.pow(i, int(p)));
if(abs(no - n) < 0.000001):
x = i;
break;
return x;
def isLevelExponential(L):
x = find_x(L[0]);
for i in range(1, len(L)):
if (not is_key(L[i], x)):
return False;
return True;
def printExponentialLevels(Lev):
for x in Lev:
print(x, end = ' ')
print()
# Function to find Exponential levels in the tree
def find_ExponentialLevels(node, queue,
index, size):
Lev = []
while (index < size):
curr_size = size;
while index < curr_size:
temp = queue[index];
Lev.append(temp.key);
if (temp.left != None):
queue[size] = temp.left;
size += 1
if (temp.right != None):
queue[size] = temp.right;
size += 1
index += 1;
if (isLevelExponential(Lev)):
printExponentialLevels(Lev);
Lev.clear();
# Method that will help in finding the total no of nodes in the binary tree.
def findSize(node):
if (node == None):
return 0;
return (1 + findSize(node.left) +
findSize(node.right));
# Function to print Exponential levels in the tree.
def printExponentialLevel(node):
t_size = findSize(node);
queue=[0 for i in range(t_size)]
queue[0] = node;
find_ExponentialLevels(node, queue,
0, 1);
# The main method.
if __name__ == "__main__":
root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(16);
root.left.right = newNode(2);
root.right.left = newNode(8);
root.right.right = newNode(4);
SieveOfEratosthenes();
print("The Exponential Levels of the Binary Tree are: ")
printExponentialLevel(root);
You can also try this code with Online Python Compiler
O(N), where ‘N’ is the number of nodes in the tree.
Since we are traversing the entire tree only once and at every traversal, and also we are checking whether it’s in the form of x ^ y or not, it will cost us only O(1) time. Thus the time complexity is O(N).
Space Complexity
O(N), where 'N' is the number of nodes in the tree.
Since we are using a queue for level order traversal, which will take extra O(N) space.
Frequently Asked Questions
What are Binary Trees?
If every node has at most two child nodes, the tree is termed a binary tree. A left pointer, a right pointer, and a data element make up a binary tree node. A valid binary tree is also an empty binary tree (one with 0 nodes).
What is a generic tree?
A generic tree, often known as an n-ary tree, is a tree data structure in which each node can have up to n children, with n being an integer number.
What are some of the advantages of using binary trees?
Data is inserted and deleted faster than linked lists and arrays. A hierarchical method of storing data is faster than a linked list, and it also denotes the structural relationship that exists in the data.
What is the need for balancing Binary Trees?
A balanced binary tree reduces the amount of time it takes to search through the tree. In the worst scenario, the search time complexity of a balanced binary tree is O(log n), whereas in the best situation, it is O(n), where n is the number of nodes. For huge trees, keeping a balanced tree is advantageous.
What does binary tree level order mean?
The Level Order Traversal algorithm goes over each node in a tree in order of depth, starting with the root, moving on to its children, etc.
8+ registered 