Last Updated: 6 Dec, 2020

Remove BST keys outside the given range

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now