Convert a Binary Tree to BST by left shifting digits of node values
Given a Binary Tree of positive integers. The task is to convert it to a BST using left shift operations on the digits of the nodes. If it is not possible to convert the binary tree to BST then print -1.
Examples:
Input: 443
/ \
132 543
/ \
343 237Output: 344
/ \
132 435
/ \
433 723Explanation: 443 ? left shift two times ? 344
132 ? zero shift operations ? 132
543 ? left shift one time ? 435
343 ? left shift one time ? 433
237 ? left shift two times ? 723Input: 43
/ \
56 45Output: -1
Approach: The idea is to perform Inorder traversal on the Binary Tree in increasing order because in-order traversal of a BST always generates sorted sequence. Follow the steps below to solve the problem:
- Initialize a variable, say prev = -1, to keep track of the value of the previous node.
- Then, traverse the tree using Inorder Traversal and try to convert every node to its lowest possible value greater than the previous value by left shifting its digits.
- After performing these operations, check if the binary tree is a BST or not.
- If found to be true, print the tree. Otherwise, print -1.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of a Node struct TreeNode { int val; TreeNode *left, *right; TreeNode( int key) { val = key; left = NULL; right = NULL; } }; // Function to check if // the tree is BST or not bool isBST(TreeNode *root, TreeNode *l = NULL, TreeNode *r = NULL) { // Base condition if (!root) return true ; // Check for left child if (l && root->val <= l->val) return false ; // Check for right child if (r && root->val >= r->val) return false ; // Check for left and right subtrees return isBST(root->left, l, root) and isBST(root->right, root, r); } // Function to convert a tree to BST // by left shift of its digits void ConvTree(TreeNode *root, int &prev) { // If root is NULL if (!root) return ; // Recursively modify the // left subtree ConvTree(root->left,prev); // Initialise optimal element // to the initial element int optEle = root->val; // Convert it into a string string strEle = to_string(root->val); // For checking all the // left shift operations bool flag = true ; for ( int idx = 0; idx < strEle.size(); idx++) { // Perform left shift int shiftedNum = stoi(strEle.substr(idx) + strEle.substr(0, idx)); // If the number after left shift // is the minimum and greater than // its previous element // first value >= prev // used to setup initialize optEle // cout<<prev<<endl; if (shiftedNum >= prev and flag) { optEle = shiftedNum; flag = false ; } if (shiftedNum >= prev) optEle = min(optEle, shiftedNum); } root->val = optEle; prev = root->val; // Recursively solve for right // subtree ConvTree(root->right,prev); } // Function to print level // order traversal of a tree 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; } // new line cout << endl; } // Driver Code int main() { TreeNode *root = new TreeNode(443); root->left = new TreeNode(132); root->right = new TreeNode(543); root->right->left = new TreeNode(343); root->right->right = new TreeNode(237); // Converts the tree to BST int prev = -1; ConvTree(root, prev); // If tree is converted to a BST if (isBST(root, NULL, NULL)) { // Print its level order traversal levelOrder(root); } else { // not possible cout << (-1); } } // This code is contributed by mohit kumar 29 |
Java
// Java program for the above approach import java.util.*; class GFG{ static int prev; // Structure of a Node static class TreeNode { int val; TreeNode left, right; TreeNode( int key) { val = key; left = null ; right = null ; } }; // Function to check if // the tree is BST or not static boolean isBST(TreeNode root, TreeNode l, TreeNode r) { // Base condition if (root == null ) return true ; // Check for left child if (l != null && root.val <= l.val) return false ; // Check for right child if (r != null && root.val >= r.val) return false ; // Check for left and right subtrees return isBST(root.left, l, root) & isBST(root.right, root, r); } // Function to convert a tree to BST // by left shift of its digits static void ConvTree(TreeNode root) { // If root is null if (root == null ) return ; // Recursively modify the // left subtree ConvTree(root.left); // Initialise optimal element // to the initial element int optEle = root.val; // Convert it into a String String strEle = String.valueOf(root.val); // For checking all the // left shift operations boolean flag = true ; for ( int idx = 0 ; idx < strEle.length(); idx++) { // Perform left shift int shiftedNum = Integer.parseInt( strEle.substring(idx) + strEle.substring( 0 , idx)); // If the number after left shift // is the minimum and greater than // its previous element // first value >= prev // used to setup initialize optEle // System.out.print(prev<<endl; if (shiftedNum >= prev && flag) { optEle = shiftedNum; flag = false ; } if (shiftedNum >= prev) optEle = Math.min(optEle, shiftedNum); } root.val = optEle; prev = root.val; // Recursively solve for right // subtree ConvTree(root.right); } // Function to print level // order traversal of a tree static void levelOrder(TreeNode root) { Queue<TreeNode> que = new LinkedList<GFG.TreeNode>(); que.add(root); while ( true ) { int length = que.size(); if (length == 0 ) break ; while (length > 0 ) { TreeNode temp = que.peek(); que.remove(); System.out.print(temp.val + " " ); if (temp.left != null ) que.add(temp.left); if (temp.right != null ) que.add(temp.right); length -= 1 ; } System.out.println(); } // New line System.out.println(); } // Driver Code public static void main(String[] args) { TreeNode root = new TreeNode( 443 ); root.left = new TreeNode( 132 ); root.right = new TreeNode( 543 ); root.right.left = new TreeNode( 343 ); root.right.right = new TreeNode( 237 ); // Converts the tree to BST prev = - 1 ; ConvTree(root); // If tree is converted to a BST if (isBST(root, null , null )) { // Print its level order traversal levelOrder(root); } else { // not possible System.out.print(- 1 ); } } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Structure of a Node class TreeNode: def __init__( self , key): self .val = key self .left = None self .right = None # Function to check if # the tree is BST or not def isBST(root, l = None , r = None ): # Base condition if not root: return True # Check for left child if l and root.val < = l.val: return False # Check for right child if r and root.val > = r.val: return False # Check for left and right subtrees return isBST(root.left, l, root) and isBST(root.right, root, r) # Function to convert a tree to BST # by left shift of its digits def ConvTree(root): global prev # If root is NULL if not root: return # Recursively modify the # left subtree ConvTree(root.left) # Initialise optimal element # to the initial element optEle = root.val # Convert it into a string strEle = str (root.val) # For checking all the # left shift operations flag = True for idx in range ( len (strEle)): # Perform left shift shiftedNum = int (strEle[idx:] + strEle[:idx]) # If the number after left shift # is the minimum and greater than # its previous element # first value >= prev # used to setup initialize optEle if shiftedNum > = prev and flag: optEle = shiftedNum flag = False if shiftedNum > = prev: optEle = min (optEle, shiftedNum) root.val = optEle prev = root.val # Recursively solve for right # subtree ConvTree(root.right) # Function to print level # order traversal of a tree def levelOrder(root): que = [root] while True : length = len (que) if not length: break 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 # new line print () # Driver Code root = TreeNode( 443 ) root.left = TreeNode( 132 ) root.right = TreeNode( 543 ) root.right.left = TreeNode( 343 ) root.right.right = TreeNode( 237 ) # Initialize to # previous element prev = - 1 # Converts the tree to BST ConvTree(root) # If tree is converted to a BST if isBST(root, None , None ): # Print its level order traversal levelOrder(root) else : # not possible print ( - 1 ) |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { static int prev; // Structure of a Node class TreeNode { public int val; public TreeNode left, right; public TreeNode( int key) { val = key; left = null ; right = null ; } }; // Function to check if // the tree is BST or not static bool isBST(TreeNode root, TreeNode l, TreeNode r) { // Base condition if (root == null ) return true ; // Check for left child if (l != null && root.val <= l.val) return false ; // Check for right child if (r != null && root.val >= r.val) return false ; // Check for left and right subtrees return isBST(root.left, l, root) & isBST(root.right, root, r); } // Function to convert a tree to BST // by left shift of its digits static void ConvTree(TreeNode root) { // If root is null if (root == null ) return ; // Recursively modify the // left subtree ConvTree(root.left); // Initialise optimal element // to the initial element int optEle = root.val; // Convert it into a String String strEle = String.Join( "" , root.val); // For checking all the // left shift operations bool flag = true ; for ( int idx = 0; idx < strEle.Length; idx++) { // Perform left shift int shiftedNum = Int32.Parse( strEle.Substring(idx) + strEle.Substring(0, idx)); // If the number after left shift // is the minimum and greater than // its previous element // first value >= prev // used to setup initialize optEle // Console.Write(prev<<endl; if (shiftedNum >= prev && flag) { optEle = shiftedNum; flag = false ; } if (shiftedNum >= prev) optEle = Math.Min(optEle, shiftedNum); } root.val = optEle; prev = root.val; // Recursively solve for right // subtree ConvTree(root.right); } // Function to print level // order traversal of a tree static void levelOrder(TreeNode root) { Queue<TreeNode> que = new Queue<GFG.TreeNode>(); que.Enqueue(root); while ( true ) { int length = que.Count; if (length == 0) break ; while (length > 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); length -= 1; } Console.WriteLine(); } // New line Console.WriteLine(); } // Driver Code public static void Main(String[] args) { TreeNode root = new TreeNode(443); root.left = new TreeNode(132); root.right = new TreeNode(543); root.right.left = new TreeNode(343); root.right.right = new TreeNode(237); // Converts the tree to BST prev = -1; ConvTree(root); // If tree is converted to a BST if (isBST(root, null , null )) { // Print its level order traversal levelOrder(root); } else { // not possible Console.Write(-1); } } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach let prev; // Structure of a Node class TreeNode { constructor(key) { this .left = null ; this .right = null ; this .val = key; } } // Function to check if // the tree is BST or not function isBST(root, l, r) { // Base condition if (root == null ) return true ; // Check for left child if (l != null && root.val <= l.val) return false ; // Check for right child if (r != null && root.val >= r.val) return false ; // Check for left and right subtrees return isBST(root.left, l, root) & isBST(root.right, root, r); } // Function to convert a tree to BST // by left shift of its digits function ConvTree(root) { // If root is null if (root == null ) return ; // Recursively modify the // left subtree ConvTree(root.left); // Initialise optimal element // to the initial element let optEle = root.val; // Convert it into a String let strEle = (root.val).toString(); // For checking all the // left shift operations let flag = true ; for (let idx = 0; idx < strEle.length; idx++) { // Perform left shift let shiftedNum = parseInt( strEle.substring(idx) + strEle.substring(0, idx)); // If the number after left shift // is the minimum and greater than // its previous element // first value >= prev // used to setup initialize optEle // Console.Write(prev<<endl; if (shiftedNum >= prev && flag) { optEle = shiftedNum; flag = false ; } if (shiftedNum >= prev) optEle = Math.min(optEle, shiftedNum); } root.val = optEle; prev = root.val; // Recursively solve for right // subtree ConvTree(root.right); } // Function to print level // order traversal of a tree function levelOrder(root) { let que = []; que.push(root); while ( true ) { let length = que.length; if (length == 0) break ; while (length > 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); length -= 1; } document.write( "</br>" ); } // New line document.write( "</br>" ); } let root = new TreeNode(443); root.left = new TreeNode(132); root.right = new TreeNode(543); root.right.left = new TreeNode(343); root.right.right = new TreeNode(237); // Converts the tree to BST prev = -1; ConvTree(root); // If tree is converted to a BST if (isBST(root, null , null )) { // Print its level order traversal levelOrder(root); } else { // not possible document.write(-1); } </script> |
344 132 435 433 723
Time Complexity: O(N)
Auxiliary Space: O(N)