I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h)
where s is the number of keys to remove and h is the height of the tree.
The naive solution is just to find nodes in range and delete them and fix the tree one-by-one, but that doesn't meet the time complexity requirement as it would be O(s * h).
I have considered the fact that if a node is within the range and its left child is in range, all of the left child's right children are in range as well as if the right child of the node is in range, the left children of the right child are also in range. Both of these facts allow you to delete the entire subtree below those children by simply unlinking it. I'm having trouble converting this information into a useful algorithm.