[Java] Test whether a tree is a valid BST

Given a binary tree without repeated elements, we want to test if that tree also a valid binary search tree.

A BST is a tree where each node must respect the property that its location with respect to its parent will be on the left side is the node's value is less than the parent's value, otherwise it will be on the right side.

This means that when inserting a node we move left or right until we find the correct location for a node and its location is constrained by values coming from previous levels, for example a node X can NEVER be in the RIGHT subtree of a node that has a higher value than X.

We can therefore use a recursive approach to visit the whole tree, setting the correct boundaries at each call. If a node is out of those boundaries, the tree is NOT a BST.

Another approach would be to perform an inorder visit of the BST, which should return the elements in their natural order IF the tree is a valid BST. Therefore we can scan the elements in this visit and test whether each one is smaller than the next.

Both approaches are O(N) time.

You can find my implementation of isValidBST and isValidBSTWithInorderVisit on my Gist along with some tests in BSTJTests.