Modify BST

PROBLEM STATEMENT

You are given the root of a binary search tree ‘TREE’ and the lowest and highest boundaries as ‘LOW’ and ‘HIGH’. Your task is to modify the tree so that all its nodes have values in the range [‘LOW’, ‘HIGH’] inclusive.

Modifying the tree should not change the relative structure of the nodes that will remain in the tree (i.e., any node's descendant should remain a descendant). There will always be a unique answer.

Note that the root may change depending on the given bounds.

For example: For ‘LOW’ = 3 and ‘HIGH’ = 6 see the below picture for reference:

As we can see 0 is not in the range [3, 6] so we delete this node from the ‘TREE’.

Input Format:

The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains two single space-separated integers ‘LOW’ and ‘HIGH’.

The second line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

4
2 6
1 3 5 7
-1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = 2
Right child of 4 = 6

Level 3 :
Left child of 2 = 1
Right child of 2 = 3
Left child of 6 = 5
Right child of 6 = 7

Level 4 :
Left child of 1 = null (-1)
Right child of 1 = null (-1)
Left child of 3 = null (-1)
Right child of 3 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).

Note :

The above format was just to provide clarity on how the input is formed for a given tree. 

The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1

Output Format :

For each test case, print the modified tree after trimming in the level order form.

The output for each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100
1 <= N <= 10 ^ 4
1 <= DATA <= 10 ^ 4 
1 <= LOW , HIGH <= 10 ^ 4

Where N is the number of nodes in the ‘TREE’, ‘DATA’ represents the value of the node.

Time Limit: 1 Sec

Approach 1

The idea behind this approach is to use the following properties of BST:

Values of the nodes in the left subtree of a node must be less than the value of the current node.
Values of the nodes in the right subtree of a node must be greater than the value of the current node.

Now we do inorder traversal on ‘TREE’ and we need to handle the following cases:

If the node value is in the range [‘LOW’, ‘HIGH’]:
- We need to return this node, but we may need to modify its left and right subtrees.
Else if the node value is less than ’LOW’:
- Because of the binary search tree property, the value of the node as well as the value of all the nodes in the left subtree is not in range. So we need to return the modified right subtree.
Else if the node value is greater than ‘HIGH’:
- Because of the binary search tree property, the value of the node as well as the value of all the nodes in the right subtree is not in range. So we need to return the modified left subtree.

Here is the complete algorithm:

We call out recursive function ‘INORDERTRAVERSAL’ having parameters ‘CURRNODE’ representing the current node of the ‘TREE’ and ‘LOW’ and ‘HIGH’ respectively.
Initially, we pass the root as ‘CURRNODE’.
If the value of ‘CURRNODE’ is ‘NULL’, we simply return ‘NULL’.
If the value of the ‘CURRNODE’ is less than ‘LOW’.
- We call ‘INORDERTRAVERSAL’ function and pass ‘CURRNODE -> RIGHT’ as ‘CURRNODE’.
- Return the node returned by this call.
If the value of the ‘CURRNODE’ is greater than ‘HIGH’:
- We call ’INORDERTRAVERSAL’ function and pass ‘CURRNODE→LEFT’ as ‘CURRNODE’.
- Return the node returned by this call.
If the value of ‘CURRNODE’ is in range then do the following:
- Call ‘INORDERTRAVERSAL’ and pass ‘CURRNODE -> LEFT’ as ‘CURRNODE’ and assign the modified left subtree to the left of ‘CURRNODE’.
- Call ‘INORDERTRAVERSAL’ and pass ‘CURRNODE -> RIGHT’ as ‘CURRNODE’ and assign the modified right subtree to the right of ‘CURRNODE’.
Finally, return ‘CURRNODE’.

Try Problem

Approach 2

Approach: We will use the properties of BST as discussed in the previous approach. But in this approach, we will use stack.

Here is the complete algorithm:

Make a stack ‘ST’ of type ‘NODE’ and a ‘FLAG’ = false. We use ‘FLAG’ to track the node which is not in the range.
Initially, we remove all the nodes which are not in range. Following is the algorithm for doing this:
- Run a while loop while the value of ‘ROOT’ is less than ‘LOW’ or greater than ‘HIGH’.
  - If the value of the root is less than ‘LOW’, ‘ROOT’ = ‘ROOT’ -> ‘RIGHT’.
  - If value of root is greater than ‘HIGH’, ‘ROOT’ = ‘ROOT’ -> ‘LEFT’.
Push ‘ROOT’ into the stack and while the stack is not empty do the following:
- Pop the top node from the stack and store it in a variable ‘NODE’.
- If a left child of ‘NODE’ is not NULL and less than ‘LOW’ do the following:
  - Replace the left child with the right child of the left node.
  - ‘FLAG’ = true.
- If a right child of ‘NODE’ is not NULL and greater than ‘HIGH’ do the following:
  - Replace the right child with the left child of the right node.
  - ‘FLAG’ = true.
- If ‘FLAG’ is true then push ‘NODE’ into the stack.
- Else handle the following two cases:
  - If the left child of ‘NODE’ exists then push it into the stack.
  - If the right child of ‘NODE’ exists then push it into the stack.
- Make the ‘FLAG’ = false.
Finally return the ‘ROOT’.