Modify BST

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
7 upvotes
Asked in companies
MicrosoftAppleNetmeds

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:

img

As we can see 0 is not in the range [3, 6] so we delete this node from the ‘TREE’.
Detailed explanation ( Input/output format, Notes, Images )
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 :

image

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
Sample Input 1 :
2
1 5
3 -1 -1
2 8
1 0 9 -1 -1 -1 -1
Sample Output 1:
3 -1 -1
-1

Explanation Of Sample Output 1:

For the first test case :
There is only one node in the ‘TREE’ which lies in the given range 1 <= 3 <= 5
So in this case we don’t need to delete any node from the ‘TREE’.

For the second test case :
All the nodes in the ‘TREE’ are not in the range so every node gets deleted from the ‘TREE’. So we return NULL in this case.
Sample Input 2 :
2
1 6
3 0 8 -1 2 -1 -1 1 -1 -1 -1
5 5
5 -1 6 -1 -1
Sample Output 2 :
3 2 -1 1 -1 -1 -1 
5 -1 -1

Explanation Of Sample Output 2:

For the first test case :
Nodes marked blue are not in the range so we will delete these nodes.

img

For the second test case :
Node marked blue is not in the range so we will delete this node.

img

Hint

Use inorder traversal in this problem to get final tree.

Approaches (2)
Recursion

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:

  1. We call out recursive function ‘INORDERTRAVERSAL’ having parameters ‘CURRNODE’ representing the current node of the ‘TREE’ and ‘LOW’ and ‘HIGH’ respectively.
  2. Initially, we pass the root as ‘CURRNODE’.
  3. If the value of ‘CURRNODE’ is ‘NULL’, we simply return ‘NULL’.
  4. 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.
  5. 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.
  6. 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’.
  7. Finally, return ‘CURRNODE’.
Time Complexity

O(N), where N represents the number of nodes in the ‘TREE’.

 

Because in the worst case when 'TREE’ is skewed and each node’s value in the ‘TREE’ is in range, we will traverse each node in the ‘TREE’ exactly once. Hence, time complexity will be O(N).

Space Complexity

O(N), where N represents the number of nodes in the ‘TREE’.

 

Because in the case of the skewed tree and all the node’s values are in range so the recursion stack will be of size N. Hence overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Modify BST
Full screen
Console