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.
Got a thought to share or found a bug in the code? We'd love to hear from you:
It might be tempting to think that the above code does not work when