Binary Search Trees

Remove nodes in BST which are outside the given range:

Given a binary search tree(BST) and a range of numbers ['min' to 'max'], remove all nodes of a given BST which are not in the given range. Any node having value less than 'min' or having value greater than 'max' should be removed. The condition is that after removing the nodes, modified BST should be still a BST.

Example :

                                  

HINT:

In a BST, for every subtree the value of root is always greater than its  left subtree and value of root is always lesser than its right subtree

 There are 2 possible cases:

•         The value of the node is smaller than the min value.

 In this case, since the value of the node is smaller than the min value, the nodes in its left subtree would also be smaller than the min value.So, return its right subtree.

•         The value of the node is greater than max value.

            In this case, nodes in its right subtree would also be greater than max.So return its left subtree to the caller.

FUNCTION PROGRAM:

struct Node*  removeOutOfRange(Node* root,int min,int max)

{

     if(root==NULL) return NULL; /* Base Case */

          root->left = removeOutOfRange(root->left,min,max);

  

          root->right=removeOutOfRange(root->right,min,max ;

/* Case 1 */

     if(root->data<min)

     {

         struct Node* temp=root->right;

         free(root);

         return temp;

      }

/ * Case 2 */

     if(root->data>max)

    {

          struct Node* temp=root->left;

          free(root);

          return temp;

    }

 return root;

}