Remove nodes outside a given range - PrismoSkills

Remove nodes outside a given range - PrismoSkills
Problem: Given a binary search tree and a range, remove nodes from the tree which fall outside this range.


Solution: An easy way to do this is to write out the tree into a sorted array during inorder traversal.
Then remove the elements from this array which do not come inside the range.
And then construct binary search tree from the remaining list.
Order for this approach is 3*O(n) and space requirement is O(n)

A better solution can be done in O(n) and O(1) space by modifying the tree itself during traversa
http://www.geeksforgeeks.org/remove-bst-keys-outside-the-given-range/

here are two possible cases for every node.
1) Node’s key is outside the given range. This case has two sub-cases.
…….a) Node’s key is smaller than the min value.
…….b) Node’s key is greater that the max value.
2) Node’s key is in range.

We don’t need to do anything for case 2. In case 1, we need to remove the node and change root of sub-tree rooted with this node.

The idea is to fix the tree in Postorder fashion. When we visit a node, we make sure that its left and right sub-trees are already fixed. In case 1.a), we simply remove root and return right sub-tree as new root. In case 1.b), we remove root and return left sub-tree as new root.

// Resmoves all nodes having value outside the given range and returns the root

// of modified tree

node* removeOutsideRange(node *root, int min, int max)

{

   // Base Case

   if (root == NULL)

      return NULL;

   // First fix the left and right subtrees of root

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

   root->right =  removeOutsideRange(root->right, min, max);

   // Now fix the root.  There are 2 possible cases for toot

   // 1.a) Root's key is smaller than min value (root is not in range)

   if (root->key < min)

   {

       node *rChild = root->right;

       delete root;

       return rChild;

   }

   // 1.b) Root's key is greater than max value (root is not in range)

   if (root->key > max)

   {

       node *lChild = root->left;

       delete root;

       return lChild;

   }

   // 2. Root is in range

   return root;

}

TreeNode removeOutsideRange (TreeNode root, int low, int high)
{
    if (root == null)
        return;

    root.left  = removeOutsideRange (root.left,  low, high);
    root.right = removeOutsideRange (root.right, low, high);

    if (root.data < low)
        return root.right;

    if (root.data > high)
        return root.left;

    return root;
}

This can also be done using preorder:

void distroy(node * root)
{
if(root==NULL)
return ;
distroy(root->left);
distroy(root->right);
free(root);
}

node *removeOutsideRange(node* root,int k1,int k2)
{

if(root==NULL)
return NULL;
if(root->data>=k1 && root->data<=k2)
{
root->left=removeOutsideRange(root->left,k1,k2);
root->right=removeOutsideRange(root->right,k1,k2);
}
else
if(root->data < k1 )
{
node* temp=root->right;
distroy(root->left);
delete (root);
return removeOutsideRange(temp,k1,k2);
}
else if(root->data>k2)
{
node* temp=root->left;
distroy(root->right);
delete (root);
return removeOutsideRange(temp,k1,k2);
}

return root;
}

Please read full article from Remove nodes outside a given range - PrismoSkills