Dylan Siegler - 8 months ago 32

Java Question

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

`BinarySearchTree`

`BinarySearchTree`

`minimum`

`IllegalArgumentException`

`BinarySearchTreeNode`

`BinaryTreeNode`

`BinarySearchTreeNode`

`isValidBinaryTree`

`BinarySearchTreeNode`

Just for reference you don't really need to know what a binary search tree is. It is just a type of binary tree (each node has 0-2 children) where the value of the left child is <= the value of the parent and the value of the right child is >= the value of the parent for all nodes in the tree (this is what I refer to as a valid tree).

Answer

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 `add`

and `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.