Dylan Siegler Dylan Siegler - 1 year ago 62
Java Question

Where to Add Checks for Validity in a Binary Search Tree

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

class, but I'm not sure where to put the checks to make sure that it is a valid
. Currently I have no checks, but I am considering checking before every relevant operation on that tree (i.e. check before searching, check before doing a tree walk, check before
, etc) as well as when the tree is constructed. If the tree isn't valid then I will throw an
. However, before I implemented this I considered instead making a new
class which extends
(which is the class I am currently using) and instead making the checks in the
class (on construction and whenever the children are set). So, I don't need an implementation of any of this (I already have an
method), but which is best practice: never checking if the tree is valid, checking if the tree is valid during the construction of the tree and before each method call on the tree, or making a
class which checks during construction and whenever the children are set?

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 Source

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.