# 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.
#=======================================================================

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: