Given a Binary Search Tree and a range [L, R] , write a program to remove all keys which are outside the given range.

Problem Note

  • You might need to change the root of the tree, so the result should return the new root of the modified BST.
  • The modified tree should also be a BST.

Example 1

            18         
           /   \       
         -4     24
         / \    / \
       -8  12  20  28
           / \
          9  14
Input: Consider the following BST and range [6, 22]
Output: The given tree should be changed to following
           18         
          /  \       
        12    20
       /  \
      9   14
Explanation: All keys outside the range [6, 22] are removed and modified tree is BST.