Given a Binary Tree, the task is to modify the Tree by left rotating every node any number of times such that every level consists of node values in increasing order from left to right. If it is not possible to arrange node values of any level in increasing order, then print “-1”.
Examples:
Input:
341
/ \
241 123
/ \ \
324 235 161
Output:
341
/ \
124 231
/ \ \
243 352 611
Explanation:
Level 1: The value of the root node is 341, having all digits sorted.
Level 2: The node values are 241 and 123. Left rotating 241 twice and 231 once modifies the node values to 124 and 231.
Level 3: The node values are 342, 235 and 161. Left rotating digits of 342 once, 235 once and 161 once modifies the node values to {243, 352, 611} respectively.Input:
12
/ \
89 15Output: -1
Approach: The given problem can be solved by performing Level Order Traversal and left rotating the digits of node values to make values every level in increasing order. Follow the steps below to solve the problem:
- Initialize a queue, say Q that is used to perform the level order traversal.
- Push the root node of the tree in the queue.
- Iterate until the queue is not empty and perform the following steps:
- Find the size of the queue and store it in variable L.
- Initialize a variable, say prev that is used to store the previous element in the current level of the tree.
- Iterate over the range [0, L] and perform the following steps:
- Pop the front node of the queue and store it in a variable, say temp.
- Now, left shift the element temp and if there exists any permutation which is greater than prev and closer to prev then update the current node’s value as the value of the temp.
- Update the value of prev to the current value of temp.
- If the temp has left or right child then push it into the queue.
- After the above steps, if the current set of nodes has not ordered in increasing order, then print “No”. Otherwise, check for the next iteration.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // TreeNode class struct TreeNode { int val; TreeNode* left,*right; TreeNode( int v) { val = v; left = NULL; right = NULL; } }; // Function to check if the nodes // are in increasing order or not bool isInc(TreeNode *root) { // Perform Level Order Traversal queue<TreeNode*> que; que.push(root); while ( true ) { // Current length of queue int length = que.size(); // If queue is empty if (length == 0) break ; auto pre = que.front(); // Level order traversal while (length > 0) { // Pop element from // front of the queue auto temp = que.front(); que.pop(); // If previous value exceeds // current value, return false if (pre->val > temp->val) return false ; pre = temp; if (temp->left) que.push(temp->left); if (temp->right) que.push(temp->right); length -= 1; } } return true ; } // Function to print the Tree // after modification void levelOrder(TreeNode *root) { // Performs level // order traversal queue<TreeNode*> que; que.push(root); while ( true ) { // Calculate size of the queue int length = que.size(); if (length == 0) break ; // Iterate until queue is empty while (length) { auto temp = que.front(); que.pop(); cout << temp->val << " " ; if (temp->left) que.push(temp->left); if (temp->right) que.push(temp->right); length -= 1; } cout << endl; } cout << endl; } // Function to arrange node values // of each level in increasing order void makeInc(TreeNode *root) { // Perform level order traversal queue<TreeNode*> que; que.push(root); while ( true ) { // Calculate length of queue int length = que.size(); // If queue is empty if (length == 0) break ; int prev = -1; // Level order traversal while (length > 0) { //cout<<"loop"; // Pop element from // front of the queue auto temp = que.front(); que.pop(); // Initialize the optimal // element by the initial // element auto optEle = temp->val; auto strEle = to_string(temp->val); // Check for all left // shift operations bool flag = true ; int yy = strEle.size(); for ( int idx = 0; idx < strEle.size(); idx++) { // Left shift int ls = stoi(strEle.substr(idx, yy) + strEle.substr(0, idx)); if (ls >= prev and flag) { optEle = ls; flag = false ; } // If the current shifting // gives optimal solution if (ls >= prev) optEle = min(optEle, ls); } // Replacing initial element // by the optimal element temp->val = optEle; prev = temp->val; // Push the LST if (temp->left) que.push(temp->left); // Push the RST if (temp->right) que.push(temp->right); length -= 1; } } // Print the result if (isInc(root)) levelOrder(root); else cout << (-1); } // Driver Code int main() { TreeNode *root = new TreeNode(341); root->left = new TreeNode(241); root->right = new TreeNode(123); root->left->left = new TreeNode(324); root->left->right = new TreeNode(235); root->right->right = new TreeNode(161); makeInc(root); } // This code is contributed by mohit kumar 29 |
Java
// Java program for the above approach import java.util.*; class GFG{ // TreeNode class static class TreeNode { public int val; public TreeNode left,right; }; static TreeNode newNode( int v) { TreeNode temp = new TreeNode(); temp.val = v; temp.left = temp.right = null ; return temp; } // Function to check if the nodes // are in increasing order or not static boolean isInc(TreeNode root) { // Perform Level Order Traversal Queue<TreeNode> que = new LinkedList<>(); que.add(root); while ( true ) { // Current len of queue int len = que.size(); // If queue is empty if (len == 0 ) break ; TreeNode pre = que.peek(); // Level order traversal while (len > 0 ) { // Pop element from // front of the queue TreeNode temp = que.peek(); que.poll(); // If previous value exceeds // current value, return false if (pre.val > temp.val) return false ; pre = temp; if (temp.left != null ) que.add(temp.left); if (temp.right != null ) que.add(temp.right); len -= 1 ; } } return true ; } // Function to print the Tree // after modification static void levelOrder(TreeNode root) { // Performs level // order traversal Queue<TreeNode> que = new LinkedList<>(); que.add(root); while ( true ) { // Calculate size of the queue int len = que.size(); if (len == 0 ) break ; // Iterate until queue is empty while (len > 0 ) { TreeNode temp = que.peek(); que.poll(); System.out.print(temp.val+ " " ); if (temp.left != null ) que.add(temp.left); if (temp.right != null ) que.add(temp.right); len -= 1 ; } System.out.println(); } System.out.println(); } // Function to arrange node values // of each level in increasing order static void makeInc(TreeNode root) { // Perform level order traversal Queue<TreeNode> que = new LinkedList<>(); que.add(root); while ( true ) { // Calculate len of queue int len = que.size(); // If queue is empty if (len == 0 ) break ; int prev = - 1 ; // Level order traversal while (len > 0 ) { //cout<<"loop"; // Pop element from // front of the queue TreeNode temp = que.peek(); que.poll(); // Initialize the optimal // element by the initial // element int optEle = temp.val; String strEle = String.valueOf(optEle); // Check for all left // shift operations boolean flag = true ; int yy = strEle.length(); for ( int idx = 0 ; idx < strEle.length(); idx++) { // Left shift String s1 = strEle.substring(idx, yy); String s2 = strEle.substring( 0 , idx); String s = s1+ s2; int ls = Integer.valueOf(s); if (ls >= prev && flag) { optEle = ls; flag = false ; } // If the current shifting // gives optimal solution if (ls >= prev) optEle = Math.min(optEle, ls); } // Replacing initial element // by the optimal element temp.val = optEle; prev = temp.val; // Push the LST if (temp.left != null ) que.add(temp.left); // Push the RST if (temp.right != null ) que.add(temp.right); len -= 1 ; } } // Print the result if (isInc(root) == true ) levelOrder(root); else System.out.print(- 1 ); } // Driver code public static void main (String[] args) { TreeNode root = newNode( 341 ); root.left = newNode( 241 ); root.right = newNode( 123 ); root.left.left = newNode( 324 ); root.left.right = newNode( 235 ); root.right.right = newNode( 161 ); makeInc(root); } } // This code is contributed by offbeat |
Python3
# Python3 program for the above approach # TreeNode class class TreeNode: def __init__( self , val = 0 , left = None , right = None ): self .val = val self .left = left self .right = right # Function to check if the nodes # are in increasing order or not def isInc(root): # Perform Level Order Traversal que = [root] while True : # Current length of queue length = len (que) # If queue is empty if not length: break pre = que[ 0 ] # Level order traversal while length: # Pop element from # front of the queue temp = que.pop( 0 ) # If previous value exceeds # current value, return false if pre.val > temp.val: return False pre = temp if temp.left: que.append(temp.left) if temp.right: que.append(temp.right) length - = 1 return True # Function to arrange node values # of each level in increasing order def makeInc(root): # Perform level order traversal que = [root] while True : # Calculate length of queue length = len (que) # If queue is empty if not length: break prev = - 1 # Level order traversal while length: # Pop element from # front of the queue temp = que.pop( 0 ) # Initialize the optimal # element by the initial # element optEle = temp.val strEle = str (temp.val) # Check for all left # shift operations flag = True for idx in range ( len (strEle)): # Left shift ls = int (strEle[idx:] + strEle[:idx]) if ls > = prev and flag: optEle = ls flag = False # If the current shifting # gives optimal solution if ls > = prev: optEle = min (optEle, ls) # Replacing initial element # by the optimal element temp.val = optEle prev = temp.val # Push the LST if temp.left: que.append(temp.left) # Push the RST if temp.right: que.append(temp.right) length - = 1 # Print the result if isInc(root): levelOrder(root) else : print ( - 1 ) # Function to print the Tree # after modification def levelOrder(root): # Performs level # order traversal que = [root] while True : # Calculate size of the queue length = len (que) if not length: break # Iterate until queue is empty while length: temp = que.pop( 0 ) print (temp.val, end = ' ' ) if temp.left: que.append(temp.left) if temp.right: que.append(temp.right) length - = 1 print () # Driver Code root = TreeNode( 341 ) root.left = TreeNode( 241 ) root.right = TreeNode( 123 ) root.left.left = TreeNode( 324 ) root.left.right = TreeNode( 235 ) root.right.right = TreeNode( 161 ) makeInc(root) |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // TreeNode class class TreeNode { public int val; public TreeNode left,right; }; static TreeNode newNode( int v) { TreeNode temp = new TreeNode(); temp.val = v; temp.left = temp.right = null ; return temp; } // Function to check if the nodes // are in increasing order or not static bool isInc(TreeNode root) { // Perform Level Order Traversal Queue<TreeNode> que = new Queue<TreeNode>(); que.Enqueue(root); while ( true ) { // Current len of queue int len = que.Count; // If queue is empty if (len == 0) break ; TreeNode pre = que.Peek(); // Level order traversal while (len > 0) { // Pop element from // front of the queue TreeNode temp = que.Peek(); que.Dequeue(); // If previous value exceeds // current value, return false if (pre.val > temp.val) return false ; pre = temp; if (temp.left != null ) que.Enqueue(temp.left); if (temp.right != null ) que.Enqueue(temp.right); len -= 1; } } return true ; } // Function to print the Tree // after modification static void levelOrder(TreeNode root) { // Performs level // order traversal Queue<TreeNode> que = new Queue<TreeNode>(); que.Enqueue(root); while ( true ) { // Calculate size of the queue int len = que.Count; if (len == 0) break ; // Iterate until queue is empty while (len > 0) { TreeNode temp = que.Peek(); que.Dequeue(); Console.Write(temp.val+ " " ); if (temp.left != null ) que.Enqueue(temp.left); if (temp.right != null ) que.Enqueue(temp.right); len -= 1; } Console.Write( "\n" ); } Console.Write( "\n" ); } // Function to arrange node values // of each level in increasing order static void makeInc(TreeNode root) { // Perform level order traversal Queue<TreeNode> que = new Queue<TreeNode>(); que.Enqueue(root); while ( true ) { // Calculate len of queue int len = que.Count; // If queue is empty if (len == 0) break ; int prev = -1; // Level order traversal while (len > 0) { //cout<<"loop"; // Pop element from // front of the queue TreeNode temp = que.Peek(); que.Dequeue(); // Initialize the optimal // element by the initial // element int optEle = temp.val; string strEle = optEle.ToString(); // Check for all left // shift operations bool flag = true ; int yy = strEle.Length; for ( int idx = 0; idx < strEle.Length; idx++) { // Left shift string s1 = strEle.Substring(idx, yy - idx); string s2 = strEle.Substring(0, idx); string s = String.Concat(s1, s2); int ls = Int32.Parse(s); if (ls >= prev && flag) { optEle = ls; flag = false ; } // If the current shifting // gives optimal solution if (ls >= prev) optEle = Math.Min(optEle, ls); } // Replacing initial element // by the optimal element temp.val = optEle; prev = temp.val; // Push the LST if (temp.left != null ) que.Enqueue(temp.left); // Push the RST if (temp.right != null ) que.Enqueue(temp.right); len -= 1; } } // Print the result if (isInc(root) == true ) levelOrder(root); else Console.Write(-1); } // Driver Code public static void Main() { TreeNode root = newNode(341); root.left = newNode(241); root.right = newNode(123); root.left.left = newNode(324); root.left.right = newNode(235); root.right.right = newNode(161); makeInc(root); } } // This code is contributed by ipg2016107 |
Javascript
<script> // Javascript program for the above approach // TreeNode class class Node { constructor(v) { this .val=v; this .left= this .right= null ; } } // Function to check if the nodes // are in increasing order or not function isInc(root) { // Perform Level Order Traversal let que = []; que.push(root); while ( true ) { // Current len of queue let len = que.length; // If queue is empty if (len == 0) break ; let pre = que[0]; // Level order traversal while (len > 0) { // Pop element from // front of the queue let temp = que[0]; que.shift(); // If previous value exceeds // current value, return false if (pre.val > temp.val) return false ; pre = temp; if (temp.left != null ) que.push(temp.left); if (temp.right != null ) que.push(temp.right); len -= 1; } } return true ; } // Function to print the Tree // after modification function levelOrder(root) { // Performs level // order traversal let que = []; que.push(root); while ( true ) { // Calculate size of the queue let len = que.length; if (len == 0) break ; // Iterate until queue is empty while (len > 0) { let temp = que[0]; que.shift(); document.write(temp.val+ " " ); if (temp.left != null ) que.push(temp.left); if (temp.right != null ) que.push(temp.right); len -= 1; } document.write( "<br>" ); } document.write( "<br>" ); } // Function to arrange node values // of each level in increasing order function makeInc(root) { // Perform level order traversal let que = []; que.push(root); while ( true ) { // Calculate len of queue let len = que.length; // If queue is empty if (len == 0) break ; let prev = -1; // Level order traversal while (len > 0) { //cout<<"loop"; // Pop element from // front of the queue let temp = que[0]; que.shift(); // Initialize the optimal // element by the initial // element let optEle = temp.val; let strEle = (optEle).toString(); // Check for all left // shift operations let flag = true ; let yy = strEle.length; for (let idx = 0; idx < strEle.length; idx++) { // Left shift let s1 = strEle.substring(idx, yy); let s2 = strEle.substring(0, idx); let s = s1+ s2; let ls = parseInt(s); if (ls >= prev && flag) { optEle = ls; flag = false ; } // If the current shifting // gives optimal solution if (ls >= prev) optEle = Math.min(optEle, ls); } // Replacing initial element // by the optimal element temp.val = optEle; prev = temp.val; // Push the LST if (temp.left != null ) que.push(temp.left); // Push the RST if (temp.right != null ) que.push(temp.right); len -= 1; } } // Print the result if (isInc(root) == true ) levelOrder(root); else document.write(-1); } // Driver code let root = new Node(341); root.left = new Node(241); root.right = new Node(123); root.left.left = new Node(324); root.left.right = new Node(235); root.right.right = new Node(161); makeInc(root); // This code is contributed by patel2127 </script> |
134 124 231 243 352 611
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!