Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
2.1.
Dry Run
3.
Approach
3.1.
Code
3.1.1.
Implementation in C++
3.1.2.
Input
3.1.3.
Output
3.1.4.
Implementation in Java
3.1.5.
Output
3.1.6.
Implementation in Python
3.1.7.
Output
4.
Complexity Analysis
4.1.
Time Complexity
4.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What are Binary Trees?
5.2.
What is a generic tree?
5.3.
What are some of the advantages of using binary trees?
5.4.
What is the need for balancing Binary Trees?
5.5.
What does binary tree level order mean?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Exponential Levels of a Binary Tree

Author Saksham Gupta
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

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.

img 01

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). 

img 02

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.

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
Bootcamp

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;
}

Input

img 03

The input tree would look something like this.

Output

output

 

Implementation in Java

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);
	}
}

Output

output

 

Implementation in Python

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

 

Output

output

 

Complexity Analysis

Time Complexity

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.

Conclusion

In this article, we have studied how to write a program to Exponential Levels of a Binary Tree. We hope that this article has provided you with the help to enhance your knowledge regarding hashmap and if you would like to learn more, check out our articles on Advantages of bst over hash tableReverse a path in bst using queue, and Minimum distance between bst nodes.

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available, Take a look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Merry Learning!

Previous article
Print all Prime Levels of a Binary Tree
Next article
Subtree with given sum in a Binary Tree
Live masterclass