Is BST
by 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) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test isBST
    int t = treeTape.length;
    for (int i = 0; i < treeTape.length; i++) {
      assertTrue(BST.isBST(bst.getRoot()));
      bst.delete(treeTape[--t]);
    }
    assertEquals(0, bst.size());//has correct size
  }
}