Delete ordered sequence of numbers from BST

Question

I had this question during an exam, and I couldn't find a quick answer.

There is an array A containing some ordered numbers A=[1,3,6,9,11] and a BST with numbers as key. I have to provide an efficient recursive algorithm to delete the numbers in A from the BST.

The problem I have is not in deleting the nodes, but in how to use the fact that the array is ordered in deleting the nodes.

Can someone help me with some hints?

Answer 1

Here is one possible approach.

You could simultaneously traverse both the BST (using the standard recursive algorithm) and A (from left to right). Each of the traversals will yield elements in increasing order. You're looking for matching elements to delete them from the tree.

A naive algorithm will have O(size(BST)) time complexity.

In some cases you can avoid looking at the left subtree completely: the value of the "current" node in the tree gives you an upper bound on the values in the left subtree, so if this is smaller than the value of the "current" element of A, skip the left subtree.

You can also stop the algorithm as soon as you've exhausted A.