Remove range of keys from Binary Search Tree in O(s+h)

Question

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.

Attempted solution:

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.

Answer 1

It sounds like you almost have an algorithm. Find the vertex $u$ where the successor of $m$ is stored. Similarly, find the vertex $v$ where $n$ is stored (or its predecessor if $n$ is not in the BST).

Suppose that the range of vertices to delete is not empty (that is, the key of $u$ is smaller than, or equal to, the key of $v$) and let $w$ be the lowest common ancestor of $u$ and $v$.

Proceed as follows:

• Walk from $u$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=u$) and whenever $z$ is reached from its left child, delete $z$ and its right subtree. The left subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in red in the left figure. This takes time $O(h + d_u)$, where $d_u$ is the number of deleted vertices.

• Walk from $v$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=v$) and whenever $z$ is reached from its right child, delete $z$ and its left subtree. The right subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in blue in the left figure. This takes time $O(h + d_v)$, where $d_v$ is the number of deleted vertices.

• You are now left with the task of deleting $w$ (see the figure on the right), which can be done in $O(h)$ time using the standard deletion algorithm (if $w$ is a leaf, delete it immediately, otherwise swap $w$ with its predecessor/successor and then delete it).

The overall time required is then $O(h + d_u + d_v) = O(h + s)$.