Remove BST keys outside the given range

Easy
0/40
Average time to solve is 15m
7 upvotes
Asked in companies
PhonePePayPalSamsung R&D Institute

Problem statement

Given a Binary Search Tree (BST) and a range [min, max], remove all keys which are outside the given range. The modified tree should also be BST.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line contains the integer 'T' denoting the number of test cases. Each test case contains:

The first line of each test case contains elements of the BST in the level order form (If any node does not have a left or right child, take -1 in its place).

The second line of each test case contains two integers, 'min', and 'max' (separated by space).

Output Format:

For each test case, print 'N' space separated integers denoting the inorder traversal of modified BST.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10 ^ 5
-10 ^ 3 <= nodeVal <= 10 ^ 3

Time Limit: 1sec
Sample Input 1:
2
8 3 10 1 6 -1 14 -1 -1 4 7 13 -1 -1 -1 -1 -1 -1 -1
1 9
6 -13 14 -1 -8 13 15 -1 -1 7 -1 -1 -1 -1 -1
-10 13
Sample Output 1:
1 3 4 6 7 8 
-8 6 7 13
Explanation for Sample Input 1:
Test Case 1:



The above image shows the given BST and the range given is [-10, 13]
After removing the nodes which are not in the given range. The BST will be :


Test Case 2:



The above image shows the given BST and the range given is [1, 9]
After removing the nodes which are not in the given range. The BST will be :

Sample Input 2:
2
717 473 -1 344 -1 160 -1 -51 -1 -513 -1 -542 -1 -548 -1 -669 -1 -959 -1 -1 -1 
-712 175
957 937 -1 434 -1 270 -1 -6 -1 -175 -1 -181 -1 -403 -1 -509 -1 -625 -1 -1 -1 
-907 155
Sample Output 2:
-669 -548 -542 -513 -51 160 
-625 -509 -403 -181 -175 -6
Hint

Think about using post order traversal and for each node check if the node is lying in the given range or not.

Approaches (1)
Post Order Traversal

The idea is to traverse the BST in postorder manner in such a way that we will consider that left and right subtree is already fixed. We will consider 3 cases.

Case1: If the data of root < minimum range, then we will return root's right subtree.

Case2: If the data of root > maximum range, then we will return root's left subtree.

Case3: If the data of root lies in the range then return root to the function.

 

Approach:

  • First check the base condition i.e. if root is NULL or not, if NULL then return NULL to the function.
  • Now fix the left and right subtrees and store the result in root's left and root's right respectively.
  • Now check for condition1.
  • Similarly check for condition2
  • For condition simply return root to the given function.
Time Complexity

O(N), where ‘N’ denotes the number of nodes in the given BST.

 

As we are traversing each node once therefore overall time complexity will be O(N).

Space Complexity

O(1)

 

As constant  space is used therefore overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Remove BST keys outside the given range
Full screen
Console