# Is BSTby Isai Damier, Android Engineer @ Google

```/***************************************************************************
* Author: Isai Damier
* Title: Is BST
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
*   Indicate whether the given binary tree is a BST. isBST allows for
*   either flavors of BST: left < node < right or right < node < left.
*
* Time Complexity of Solution:
*   Best = Average = Worst = O(n).
*
* Technical Details: This is an integrity ordeal algorithm (I hope this
*   phrase catches on). First the input is allowed to make a claim; then
*   the claim is severely tested for veracity. If any contradiction is
*   found, the input fails. For instance, if an input claims to be a
*   left < node < right BST, then it is sent to lnr for its trial.
*
* Note: This function has not been fully tested for true negatives.
*    See attached unit test.
*
* RNL:
*   Assume n.left.data > n.data > n.right.data. If a counter
*   instance is found, return false. Otherwise return true.
*
* LNR:
*   Assume n.left.data < n.data < n.right.data. If a counter
*   instance is found, return false; otherwise return true.
*
* lnr and rnl are symmetrical to each other.
**************************************************************************/
public static boolean isBST(Node root) {
if (null != root) {
if (null != root.left && root.left.data < root.data) {
return lnr(root);
}
if (null != root.right && root.right.data < root.data) {
return rnl(root);
}
}
return true;
}

private static boolean rnl(Node n) {
if (null == n) {
return true;
}
if (null != n.left && n.left.data < n.data) {
return false;
}
if (null != n.right && n.right.data > n.data) {
return false;
}
return rnl(n.left) && rnl(n.right);
}

private static boolean lnr(Node n) {
if (null == n) {
return true;
}
if (null != n.left && n.left.data > n.data) {
return false;
}
if (null != n.right && n.right.data < n.data) {
return false;
}
return lnr(n.left) && lnr(n.right);
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

/*************************************************************************
* Test of isBST method, of class BST.
* A good unit tests must provide both true positives and true negatives.
* To get a true negative here would require the creation of a binary tree
* that is not a BST. No such test is provided here.
************************************************************************/
@Test
public void testIsBST() {
System.out.println(""isBST"");
BST bst = new BST();

assertTrue(BST.isBST(bst.getRoot()));

int[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
175, 225, 275, 325, 375, 35, 212, 312, 400};

for (int i : treeTape) {