Left rotate digits of node values of all levels of a Binary Tree in increasing order | C ++ program for the above approach ; TreeNode class ; Function to check if the nodes are in increasing order or not ; Perform Level Order Traversal ; Current length of queue ; If queue is empty ; Level order traversal ; Pop element from front of the queue ; If previous value exceeds current value , return false ; Function to print the Tree after modification ; Performs level order traversal ; Calculate size of the queue ; Iterate until queue is empty ; Function to arrange node values of each level in increasing order ; Perform level order traversal ; Calculate length of queue ; If queue is empty ; Level order traversal ; Pop element from front of the queue ; Initialize the optimal element by the initial element ; Check for all left shift operations ; Left shift ; If the current shifting gives optimal solution ; Replacing initial element by the optimal element ; Push the LST ; Push the RST ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TreeNode { int val ; TreeNode * left , * right ; TreeNode ( int v ) { val = v ; left = NULL ; right = NULL ; } } ; bool isInc ( TreeNode * root ) { queue < TreeNode * > que ; que . push ( root ) ; while ( true ) { int length = que . size ( ) ; if ( length == 0 ) break ; auto pre = que . front ( ) ; while ( length > 0 ) { auto temp = que . front ( ) ; que . pop ( ) ; 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 ; } void levelOrder ( TreeNode * root ) { queue < TreeNode * > que ; que . push ( root ) ; while ( true ) { int length = que . size ( ) ; if ( length == 0 ) break ; 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 ; } void makeInc ( TreeNode * root ) { queue < TreeNode * > que ; que . push ( root ) ; while ( true ) { int length = que . size ( ) ; if ( length == 0 ) break ; int prev = -1 ; while ( length > 0 ) { auto temp = que . front ( ) ; que . pop ( ) ; auto optEle = temp -> val ; auto strEle = to_string ( temp -> val ) ; bool flag = true ; int yy = strEle . size ( ) ; for ( int idx = 0 ; idx < strEle . size ( ) ; idx ++ ) { int ls = stoi ( strEle . substr ( idx , yy ) + strEle . substr ( 0 , idx ) ) ; if ( ls >= prev and flag ) { optEle = ls ; flag = false ; } if ( ls >= prev ) optEle = min ( optEle , ls ) ; } temp -> val = optEle ; prev = temp -> val ; if ( temp -> left ) que . push ( temp -> left ) ; if ( temp -> right ) que . push ( temp -> right ) ; length -= 1 ; } } if ( isInc ( root ) ) levelOrder ( root ) ; else cout << ( -1 ) ; } 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 ) ; }