BSTree BSTreeDelete(BSTree t, Key k)

which returns a new tree that does not contain k.

Can be done recursively ...

But eventually we need to remove the root of some subtree.