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