Given a Binary Tree consisting of N nodes, the task is to print the Level Order Traversal after replacing the value of each node with its nearest power of the minimum value of the previous level in the original tree.
Note: For any case of two nearest powers, select the maximum among them.
Examples:
Input: 7
/ \
4 11
/
23
Output: 7 4 11 23 N
Explanation:
- Node value at level 0 remains unchanged, i.e. 7.
- Power of 7 nearest to 4 is 71 = 7.
Power of 7 nearest to 11 is 71 = 7.
Therefore, nodes at level 1 becomes {7, 7}.- Minimum node value at level 1 is 4.
Power of 4 nearest to 23 is 44 = 16.
Therefore, node at level 2 becomes {16}.The resultant tree after completing the above operations is as follows:
7
/ \
4 11
/
23Input: 3
/ \
2 6
/ \ \
45 71 25
Output: 3 3 9 32 64 N 32
Approach: The idea is to perform the Level Order Traversal using a Queue to solve the problem.
Follow the steps below to solve the problem:
- Define a function, say nearestPow(X, Y), to find the nearest power of an integer Y:
- Find log(X) base Y and store it in a variable, say K.
- Return YK if abs(X – YK) is less than abs(Y(K + 1) – X). Otherwise, return Y(K + 1).
- Initialize two variables, say minCurr and minPrev, to store the minimum value of the current level and the minimum value of the previous level respectively.
- Initially assign minPrev = root.val and initialize a queue, say Q to store the nodes for level order traversal.
- Iterate while Q is not empty():
- Store the first node of the queue in a variable, say temp, and delete the first node from queue Q.
- Assign the value of minCurr to minPrev and update minCurr = 1018.
- Iterate over the range [0, length(Q) – 1] and update the minCurr as minCurr = min(minCurr, temp.val) and assign the nearest power of the integer minPrev to temp.val.
- In each iteration of the above step push the temp.left and temp.right if the respective nodes are not NULL.
- After completing the above steps, print the level order traversal of the updated Tree.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <cmath>#include <iostream>#include <queue>using namespace std;// Structure of a Node of a Treestruct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr) : val(val) , left(left) , right(right) { }};// Function to calculate the nearest power of an integerint nearest_pow(int x, int base){ int k = floor(log(x) / log(base)); if (abs(pow(base, k) - x) < abs(pow(base, k + 1) - x)) { return pow(base, k); } else { return pow(base, k + 1); }}// Iterative method to perform Level Order Traversalvoid print_level_order(TreeNode* root){ // Base Case if (!root) { return; } // Queue for Level Order Traversal queue<TreeNode*> q; // Enqueue root q.push(root); while (!q.empty()) { // Stores number of nodes at current level int count = q.size(); // Dequeue all nodes of the current level and // Enqueue all nodes of the next level while (count--) { TreeNode* temp = q.front(); q.pop(); cout << temp->val << " "; // Push the left subtree if not empty if (temp->left) { q.push(temp->left); } // Push the right subtree if not empty if (temp->right) { q.push(temp->right); } } }}// Function to replace each node with nearest power of// minimum value of previous levelvoid replace_nodes(TreeNode* root){ // Stores the nodes of tree to traverse in level order queue<TreeNode*> que; que.push(root); // Stores current level int lvl = 1; // Stores the minimum value of previous level int min_prev = root->val; // Stores the minimum value of current level int min_curr = root->val; // Iterate while True while (true) { // Stores length of queue int length = que.size(); // If length is zero if (length == 0) { break; } // Assign min_prev = min_curr min_prev = min_curr; min_curr = 10000000000; // Iterate over range [0, length - 1] while (length--) { // Stores current node of tree TreeNode* temp = que.front(); que.pop(); // Update min_curr min_curr = min(temp->val, min_curr); // Replace current node with nearest power of // min_prev temp->val = nearest_pow(temp->val, min_prev); // Left child is not Null if (temp->left) { // Append temp->left node in the queue que.push(temp->left); } // If right child is not Null if (temp->right) { // Append temp->right node in the queue que.push(temp->right); } } // Increment level by one lvl++; } // Function Call to perform the Level Order Traversal print_level_order(root);}int main(){ // Given Tree TreeNode* root = new TreeNode(7); root->left = new TreeNode(4); root->right = new TreeNode(11); root->left->right = new TreeNode(23); replace_nodes(root); return 0;}// This code is contributed by Potta Lokesh |
Java
// Java program for the above approachimport java.io.*;import java.util.*;// Structure of a Node of a Treeclass TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }}class GFG { // Function to calculate the nearest power of an integer static int nearest_pow(int x, int base1) { int k = (int)Math.floor(Math.log(x) / Math.log(base1)); if (Math.abs(Math.pow(base1, k) - x) < Math.abs(Math.pow(base1, k + 1) - x)) { return (int)Math.pow(base1, k); } else { return (int)Math.pow(base1, k + 1); } } // Iterative method to perform Level Order Traversal static void print_level_order(TreeNode root) { // base1 Case if (root == null) { return; } // Queue for Level Order Traversal Queue<TreeNode> q = new LinkedList<>(); // Enqueue root q.add(root); while (!q.isEmpty()) { // Stores number of nodes at current level int count = q.size(); // Dequeue all nodes of the current level and // Enqueue all nodes of the next level while (count-- > 0) { TreeNode temp = q.poll(); System.out.print(temp.val + " "); // Add the left subtree if not empty if (temp.left != null) { q.add(temp.left); } // Add the right subtree if not empty if (temp.right != null) { q.add(temp.right); } } } } // Function to replace each node with nearest power of // minimum value of previous level static void replace_nodes(TreeNode root) { // Queue for level order traversal Queue<TreeNode> que = new LinkedList<TreeNode>(); // Enqueue the root que.add(root); // Stores current level int lvl = 1; // Stores the minimum value of previous level int min_prev = root.val; // Stores the minimum value of current level int min_curr = root.val; // Iterate while the queue is not empty while (true) { // Stores number of nodes at current level int length = que.size(); // If length is zero if (length == 0) { break; } // Assign min_prev = min_curr min_prev = min_curr; min_curr = Integer.MAX_VALUE; while (length-- > 0) { // Dequeue a node from the queue TreeNode temp = que.poll(); // Update min_curr min_curr = Math.min(temp.val, min_curr); // Replace current node with nearest power // of min_prev temp.val = nearest_pow(temp.val, min_prev); // Add the left and right children to the // queue if (temp.left != null) { que.add(temp.left); } if (temp.right != null) { que.add(temp.right); } } // Increment level by one lvl++; } // Function Call to perform the Level Order // Traversal print_level_order(root); } public static void main(String[] args) { // Given Tree TreeNode root = new TreeNode(7, null, null); root.left = new TreeNode(4, null, null); root.right = new TreeNode(11, null, null); root.left.right = new TreeNode(23, null, null); replace_nodes(root); }}// This code is contributed by lokeshmvs21. |
Python3
# Python program for the above approachimport math# Structure of a Node of a Treeclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right# Function to calculate the# nearest power of an integerdef nearestPow(x, base): k = int(math.log(x, base)) if abs(base**k - x) < abs(base**(k+1) - x): return base**k else: return base**(k+1)# Iterative method to perform# Level Order Traversaldef printLevelOrder(root): # Base Case if root is None: return # Queue for Level # Order Traversal q = [] # Enqueue root q.append(root) while q: # Stores number of # nodes at current level count = len(q) # Dequeue all nodes of the current # level and Enqueue all nodes of # the next level while count > 0: temp = q.pop(0) print(temp.val, end=' ') # Push the left subtree # if not empty if temp.left: q.append(temp.left) # Push the right subtree # if not empty if temp.right: q.append(temp.right) # Decrement count by 1 count -= 1# Function to replace each node# with nearest power of minimum# value of previous leveldef replaceNodes(root): # Stores the nodes of tree to # traverse in level order que = [root] # Stores current level lvl = 1 # Stores the minimum # value of previous level minPrev = root.val # Stores the minimum # value of current level minCurr = root.val # Iterate while True while True: # Stores length of queue length = len(que) # If length is zero if not length: break # Assign minPrev = minCurr minPrev = minCurr minCurr = 1000000000000000000 # Iterate over range [0, length - 1] while length: # Stores current node of tree temp = que.pop(0) # Update minCurr minCurr = min(temp.val, minCurr) # Replace current node with # nearest power of minPrev temp.val = nearestPow(temp.val, minPrev) # Left child is not Null if temp.left: # Append temp.left node # in the queue que.append(temp.left) # If right child is not Null if temp.right: # Append temp.right node # in the queue que.append(temp.right) # Decrement length by one length -= 1 # Increment level by one lvl += 1 # Function Call to perform the # Level Order Traversal printLevelOrder(root)# Driver Code# Given Treeroot = TreeNode(7)root.left = TreeNode(4)root.right = TreeNode(11)root.left.right = TreeNode(23)replaceNodes(root) |
Javascript
<script>// JavaScript program for the above approach// Structure of a Node of a Treeclass TreeNode{ constructor(val = 0, left = null, right = null){ this.val = val this.left = left this.right = right }}// Function to calculate the// nearest power of an integerfunction nearestPow(x, base){ let k = Math.floor(Math.log(x)/ Math.log(base)) if(Math.abs(Math.pow(base,k) - x) < Math.abs(Math.pow(base,k+1) - x)) return Math.pow(base,k) else return Math.pow(base,k+1)}// Iterative method to perform// Level Order Traversalfunction printLevelOrder(root){ // Base Case if(root == null) return // Queue for Level // Order Traversal let q = [] // Enqueue root q.push(root) while(q){ // Stores number of // nodes at current level let count = q.length // Dequeue all nodes of the current // level and Enqueue all nodes of // the next level while(count > 0){ let temp = q.shift() document.write(temp.val,' ') // Push the left subtree // if not empty if(temp.left) q.push(temp.left) // Push the right subtree // if not empty if(temp.right) q.push(temp.right) // Decrement count by 1 count -= 1 } }}// Function to replace each node// with nearest power of minimum// value of previous levelfunction replaceNodes(root){ // Stores the nodes of tree to // traverse in level order let que = [root] // Stores current level let lvl = 1 // Stores the minimum // value of previous level let minPrev = root.val // Stores the minimum // value of current level let minCurr = root.val // Iterate while True while(true){ // Stores length of queue let Length = que.length // If length is zero if(!Length) break // Assign minPrev = minCurr minPrev = minCurr minCurr = 1000000000000000000 // Iterate over range [0, length - 1] while(Length){ // Stores current node of tree let temp = que.shift() // Update minCurr minCurr = Math.min(temp.val, minCurr) // Replace current node with // nearest power of minPrev temp.val = nearestPow(temp.val, minPrev) // Left child is not Null if(temp.left) // Append temp.left node // in the queue que.push(temp.left) // If right child is not Null if(temp.right) // Append temp.right node // in the queue que.push(temp.right) // Decrement length by one Length-- } // Increment level by one lvl++ } // Function Call to perform the // Level Order Traversal printLevelOrder(root)}// Driver Code// Given Treelet root = new TreeNode(7)root.left = new TreeNode(4)root.right = new TreeNode(11)root.left.right = new TreeNode(23)replaceNodes(root)// This code is contributed by shinjanpatra</script> |
C#
using System;using System.Collections.Generic;// Structure of a Node of a Treeclass TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) { this.val = val; this.left = left; this.right = right; }}class GFG { // Function to calculate the nearest power of an integer static int nearest_pow(int x, int base1) { int k = (int)Math.Floor(Math.Log(x) / Math.Log(base1)); if (Math.Abs(Math.Pow(base1, k) - x) < Math.Abs(Math.Pow(base1, k + 1) - x)) { return (int)Math.Pow(base1, k); } else { return (int)Math.Pow(base1, k + 1); } } // Iterative method to perform Level Order Traversal static void print_level_order(TreeNode root) { // base1 Case if (root == null) { return; } // Queue for Level Order Traversal Queue<TreeNode> q = new Queue<TreeNode>(); // Enqueue root q.Enqueue(root); while (q.Count > 0) { // Stores number of nodes at current level int count = q.Count; // Dequeue all nodes of the current level and // Enqueue all nodes of the next level while (count-- > 0) { TreeNode temp = q.Dequeue(); Console.Write(temp.val + " "); // Add the left subtree if not empty if (temp.left != null) { q.Enqueue(temp.left); } // Add the right subtree if not empty if (temp.right != null) { q.Enqueue(temp.right); } } } } // Function to replace each node with nearest power of // minimum value of previous level static void replace_nodes(TreeNode root) { // Stores the nodes of tree to traverse in level // order Queue<TreeNode> que = new Queue<TreeNode>(); que.Enqueue(root); // Stores current level int lvl = 1; // Stores the minimum value of previous level int min_prev = root.val; // Stores the minimum value of current level int min_curr = root.val; // Iterate while True while (true) { // Stores length of queue int length = que.Count; // If length is zero if (length == 0) { break; } // Assign min_prev = min_curr min_prev = min_curr; min_curr = Int32.MaxValue; // Iterate over range [0 length - 1] while (length-- > 0) { // Stores current node of tree TreeNode temp = que.Dequeue(); // Update min_curr min_curr = Math.Min(temp.val, min_curr); // Replace current node with nearest power // of min_prev temp.val = nearest_pow(temp.val, min_prev); // Left child is not Null if (temp.left != null) { // Append temp.left node in the queue que.Enqueue(temp.left); } // If right child is not Null if (temp.right != null) { // Append temp.right node in the queue que.Enqueue(temp.right); } } // Increment level by one lvl++; } // Function Call to perform the Level Order // Traversal print_level_order(root); } public static void Main(string[] args) { // Given Tree TreeNode root = new TreeNode(7); root.left = new TreeNode(4); root.right = new TreeNode(11); root.left.right = new TreeNode(23); replace_nodes(root); }} |
Output:
7 7 7 16
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
