Remove BST keys outside the given range

Easy

0/40

Average time to solve is 15m

7 upvotes

Asked in companies

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

Console