I know this is a really specific question, but I wasn't quite sure how to phrase it more broadly, so if you recognize the broader question here, please answer it. I have implemented most of a
Your class will have contracts. A reasonable expectation for a binary search tree would be the contract that every such tree is indeed a binary search tree. This is called an invariant.
Every operation that manipulates such a tree should do it in such a way that this invariant is never broken.
This means that for every manipulation, you need to make sure that when the method finishes, the object still represents a binary search tree with all invariants intact.
Of course, you can make this easy or hard for you by choice of the API. If your tree exposes internal methods that allow for the invariants to be broken to the public, then your design is broken.
So, you should design your public API in such a way that you can indeed keep the invariants for every public method.
For example, the empty tree is indeed a binary search tree. If your
remove methods make sure that the invariants hold (and no other methods that manipulate the state of the tree exist), then there is no reason at all to check if these invariants are true before searching. You can write a proof that they must be true at that point, if you did it right.