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.
  #=======================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  @classmethod
  def isBST( self, root ):
    if None != root:
      if None != root.left and root.left.data < root.data:
        return BST.lnr( root )

      if None != root.right and root.right.data < root.data:
        return self.rnl( root )

    return True

  @classmethod
  def rnl( self, n ):
    if n is None:
      return True

    if n.left != None and n.left.data < n.data:
      return False

    if n.right != None and n.right.data > n.data:
      return False

    return self.rnl( n.left ) and self.rnl( n.right )

  @classmethod
  def lnr( self, n ):
    if n is None:
      return True

    if n.left is not None and n.left.data > n.data:
      return False

    if n.right is not None and n.right.data < n.data:
      return False

    return self.lnr( n.left ) and self.lnr( n.right );
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #=====================================================================
  # 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.
  #=====================================================================
  def testIsBST( self ):
    bst = BST()

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

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

    for i in treeTape:
      bst.add( i )

    self.assertEquals( len( treeTape ), bst.size() ) # has correct size

    # test isBST
    t = len( treeTape )
    for i in range( len( treeTape ) ):
      self.assertTrue( BST.isBST( bst.getRoot() ) )
      t -= 1
      bst.delete( treeTape[t] )

    self.assertEquals( 0, bst.size() ) # has correct size