# Delete a range of keys in a binary search tree in better than $O(n\lg n)$?

Obviously, the brute force method of:

DeleteRange(root, low, high)
for n = low to high
if n == root.key // key found
return DeleteNode(root) // O(lg n) to delete
elseif n < root.key // in left sub-tree
root.left = DeleteRange(root.left, n, high) // recur into left sub-tree
elseif n > root.key // in right sub-tree
root.right = DeleteRange(root.right, n, high) // recur into right sub-tree
return null
return root


would take $O(n\lg n)$ time. So is there any "smarter" way of deletion that would do the same thing with less complexity, perhaps pruning entire sub-trees at once? Assume that the deleted nodes are not needed and the only concern is with returning the root of a binary search tree where the nodes between the range of two keys are deleted.

• What have you tried? Hint: Try a recursive algorithm. If root < low, what should you do? Which children of the root do you need to look at? If root > high, what then? And if low <= root <= high, what then? – D.W. Nov 24 '15 at 6:20
• Are you familiar with the technique called threading? (searchable term) – Raphael Nov 24 '15 at 8:28

You might be interested in a data structure called TeardownTree. It supports delete_range operation that works in $O(k + \log n)$ time, where $n$ is the initial number of items in the tree and $k$ is the number of items deleted (and returned to the caller). Full disclosure: I am the author.
I have to emphasize that the data structure does not support the insert operation, but is optimized for clone and delete_range. I have written up an informal description of the algorithm. With all the optimizations the code is now significantly different from that document, but it should be enough to grasp the idea.