Convert a Binary Tree to BST by Left-Shifting digits of Node Values

Problem Statement

In this problem, we will be given a binary tree, and we have to convert it into a BST by left-shifting digits of node values of the given binary tree. If it is impossible to convert the given binary tree to a BST by left-shifting digits of node values, print “Impossible to convert the given binary tree to BST by left-shifting digits of node values.”

Look at the following examples for a better understanding:

Suppose the following binary tree is given:

This binary tree can be converted to the below BST by left-shifting the node values:

Here we can see that:

By left-shifting 646 one time, we will get 466

By left-shifting 342 two times, we will get 234

By left-shifting 248 one time, we will get 482

By left-shifting 814 one time, we will get 148

By left-shifting 323 zero time, we will get 323

In the above example, we have seen how to convert a binary tree to BST by left-shifting digits of node values.

In the next section, we will discuss how to solve this problem.

Approach 

The approach is based on the property of a BST that the inorder traversal of a BST generates values in increasing order. So, the idea is to do the inorder traversal of the binary tree and modify the value of the current by left-shifting its digits. For each node, make its value the smallest possible value, greater than its previous value. Initialize a variable to keep track of the value of the previous node. This way, traverse all the tree nodes and modify the node values. But it won’t always be possible to get a value greater than the previous value by left-shifting the current node’s values. So, after we cover all the nodes, check whether the converted tree is a BST. If it is a BST, print its inorder traversal. If it is not a BST, we cannot convert the given binary tree to a BST by left-shifting the digits of node values.   

Algorithm 

1. Create a “Node” class for constructing binary trees.

2. Call a function that optimally converts a BT into a BST. After that, check whether the converted tree is a BST. If it is a BST, print its inorder traversal; else, print “Impossible to convert the given binary tree to BST by left-shifting digits of node values.”

3.  Create a function “convertBinaryTree(),” which will take two inputs, a pointer to the current node and the value of the previous node, and try to convert the given binary tree to a BST. Initially previous would be -1 because there is no previous for the root node.

4. Inside the “convertBinaryTree()” function, the base case would be if the node is null, then return null. If not a null node, call the function recursively to convert the left subtree, then modify the current node's value as the lowest value greater than the previous by left-shifting its digits. After modifying the current node, call the function recursively to convert the right subtree.

5. Next, create a function “checkForBST(),” which will take the root node of a binary tree as input and return true if it is a BST, else return false. Inside the function, write the base case; if the node is null, return true. Then if the left child and right child exist, check if their values violate the condition of BST, and return false. If they don’t violate, call the function recursively to check for the left and right subtree.

6. Finally, create a function “inorder(),” which will take the root of the binary tree and print its inorder traversal.

Dry Run

Let us consider the sample case. We are given the BT shown below,

Step-1

Initially, the previous value is -1, and since we are following the inorder, the first node would be the leftmost node in the tree.

So after left shifting the digits, the minimum value we get, which is greater than the previous, is 148. Previous would be now updated to 148.

Step-2

In the second step, the next node we will visit is the left subtree's root node.

This time the previous value was 148, so we will left shift the original digits of 342 such that the obtained value is greater than the previous value. The previous value will be updated to 234.

Step-3

In this step, we will visit the right node of the left subtree.

The value would not change here because no such value is obtained after the left shifting digits of 323, which is greater than the previous value but less than the current value. Now, the previous value will be updated to 323.

Step-4

In this step, the recursive call will return to the root node because we have processed the left subtree.

Here the original value would be changed to 466 after left shifting the digits, and the previous value will be now updated to this value of 466.

Step-5

This would be the last step; here, the right subtree would be processed, and since the right subtree has only one node, the process will end after processing that node.

Here, the previous value is 466, so we will shift to increase the value such that it is just greater than 466. So after left shifting the digits, we would get 482, which is just greater than 466.

Implementation in C++

// C++ program to convert a binary tree to BST by left-shifting digits of node values
#include <bits/stdc++.h>
using namespace std;

// Node class for creating trees
class Node
{
public:
    int data;
    Node *left, *right;

    Node(int value)
    {
        this->data = value;
        this->left = NULL;
        this->right = NULL;
    }
};

// Function to convert a binary tree to BST by left-shifting digits of node values
void convertBinaryTree(Node *root, int &previous)
{

    // If root is NULL
    if (root == NULL)
    {
        return;
    }

    // Call the function recursively to convert the left subtree
    convertBinaryTree(root->left, previous);

    // Initialise the required value for the current node to the initial element
    int req_value = root->data;

    // Convert it into a string
    string str_reqValue = to_string(root->data);

    // Check for all the left shift operations of the string value
    bool flag = true;
    for (int i = 0; i < str_reqValue.size(); i++)
    {

        // left shift
        int leftShiftedVal = stoi(str_reqValue.substr(i) + str_reqValue.substr(0, i));

        if (leftShiftedVal >= previous && flag == true)
        {
            req_value = leftShiftedVal;
            flag = false;
        }

        if (leftShiftedVal >= previous)
        {
            req_value = min(req_value, leftShiftedVal);
        }
    }

    // Update the root's data with the req_value
    root->data = req_value;

    // Update the previous
    previous = root->data;

    // Call the function recursively for right subtree
    convertBinaryTree(root->right, previous);
}

// Function to check if a binary tree is BST or not
bool checkForBST(Node *root, Node *left = NULL, Node *right = NULL)
{

    // Base condition
    if (root == NULL)
    {
        return true;
    }

    // Check for left child
    if (left != NULL && left->data >= root->data)
    {
        return false;
    }

    // Check for right child
    if (right != NULL && right->data <= root->data)
    {
        return false;
    }

    // Call the function recursively for left and right subtrees
    return checkForBST(root->left, left, root) && checkForBST(root->right, root, right);
}

// Function to print in order traversal of the BST
void inOrder(Node *node)
{
    // Base case
    if (node == NULL)
        return;

    // Call the function for left child
    inOrder(node->left);

    // Print the current node's data
    cout << node->data << " ";

    // Call the function for right child
    inOrder(node->right);
}

// Driver Code
int main()
{
    // Create a binary tree
    Node *root = new Node(646);
    root->left = new Node(342);
    root->right = new Node(248);
    root->left->left = new Node(814);
    root->left->right = new Node(323);

    // Call the function to convert a binary tree to BST by left-shifting digits of node values
    int previous = -1;
    convertBinaryTree(root, previous);

    // Check if the binary tree is converted to a BST in the previous step
    if (checkForBST(root, NULL, NULL))
    {
        // Print its in order traversal
        cout << "The inorder traversal of converted BST: ";
        inOrder(root);
    }
    else
    {
        // Not possible
        cout << "Not possible to convert the given binary tree to BST by left-shifting digits of node values";
    }
}

You can also try this code with Online C++ Compiler

Run Code

Output

The inorder traversal of converted BST: 148 234 323 466 482

Algorithm Complexity

Time Complexity: O(N)

In the above approach to convert a binary tree to BST by left-shifting digits of Node values, we have created three functions - the first for converting, the second for checking if a tree is BST or not, and the third for printing the inorder traversal. Each of these functions takes O(1) time for each node. So, the overall time complexity is O(N), where ‘N’ is the number of nodes in the given binary tree.

Space Complexity: O(1) 

In the above approach, we have used constant space to convert a binary tree to BST by left-shifting digits of Node values. So, the space complexity is O(1).

Frequently asked questions-

What is a Binary Search Tree?

BST (Binary Search Tree) is a special binary tree in which there is a condition that all the nodes in the left subtree of any node will have a value less than that of the node, and all the nodes in the right subtree of the node will have a value greater than the value of the node.

What does “left shifting digits of node values” mean in this problem?

The left shifting digits of node values in the problem means shifting each digit of the node’s value to its left. According to the question, we can do this left shifting of digits as many times as we want. 

Suppose the value associated with a node is “342”; if we shift each digit to its left once, we will get “423”. Note here that the leftmost digit doesn’t have a position to its left where it can go, so it will be taken to the rightmost position, which will be vacant after shifting the remaining digits to its left.

How does a BST work?

A BST works by storing nodes hierarchically containing data, such that the left subtree of a node contains only nodes with values less than the value of the node, and the right subtree of a node contains only nodes with values greater than the value of the node.

How can you balance a BST?

There are several algorithms available for balancing a BST, such as the AVL tree and Red-Black tree algorithms. These algorithms can be used to ensure that the tree remains balanced, improving its performance and efficiency.

What is the worst-case time complexity for operations on a BST?

The worst-case time complexity for operations on a BST is O(n), which occurs when the tree is unbalanced and resembles a linked list.

Conclusion

In this article, we discussed the problem “Convert a Binary Tree to BST by Left-Shifting digits of Node Values”, the solution approach to this problem,  its C++ implementation, and its time and space complexity. If you want to solve more problems on tree data structure for practice, you can visit Coding Ninjas Studio.

I hope this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem, and if you want to learn more, check out our articles on Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the interview bundle for placement preparations.

Check out this problem - Diameter Of Binary Tree

Nevertheless, you may consider our paid courses to give your career an edge over others!

Until then, All the best for your future endeavors, and Keep Coding.