Make delicious recipes!

Remove nodes outside a given range



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 traversal.


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;
}


It might be tempting to think that the above code does not work when
root.data < low && root.right.data < low or when root.data > high && root.left.data > high because
of the wrong tree formation at lines 7 and 8 above.

However, we assure you that it is not so and the code works for both the cases.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal