In [1]:

    

class BinaryTreeNode:

    def __init__(self, value):
        self.value = value
        self.left  = None
        self.right = None

    def insert_left(self, value):
        self.left = BinaryTreeNode(value)
        return self.left

    def insert_right(self, value):
        self.right = BinaryTreeNode(value)
        return self.right


    

In [29]:

    

def check_bst(tree, minv = None, maxv = None):
    if tree is None:
        return True
    
    # initialize minmax
    if minv is None or maxv is None:
        minv, maxv = float('-inf'), float('inf')
    
    print 'node %s, minv %s, maxv %s' % (tree.value, minv, maxv)
    if node_is_valid(tree, minv, maxv):        
        return check_bst(tree.left, minv, tree.value) and check_bst(tree.right, tree.value, maxv)
    else:
        return False


def node_is_valid(tree, minv, maxv):
    right_valid = tree.right is None or (maxv >= tree.right.value >= tree.value)
    left_valid = tree.left is None or (minv <= tree.left.value <= tree.value)
    print 'right? %s, left? %s, node %s, min %s, max %s' % (right_valid, left_valid, tree.value, minv, maxv)
    return right_valid and left_valid


    

In [30]:

    

tree = BinaryTreeNode(100)
check_bst(tree)


    

    




node 100, minv -inf, maxv inf
right? True, left? True, node 100, min -inf, max inf






    
Out[30]:





True

In [31]:

    

tree.left = BinaryTreeNode(80)
check_bst(tree)


    

    




node 100, minv -inf, maxv inf
right? True, left? True, node 100, min -inf, max inf
node 80, minv -inf, maxv 100
right? True, left? True, node 80, min -inf, max 100






    
Out[31]:





True

In [32]:

    

tree.right = BinaryTreeNode(105)
check_bst(tree)


    

    




node 100, minv -inf, maxv inf
right? True, left? True, node 100, min -inf, max inf
node 80, minv -inf, maxv 100
right? True, left? True, node 80, min -inf, max 100
node 105, minv 100, maxv inf
right? True, left? True, node 105, min 100, max inf






    
Out[32]:





True

In [34]:

    

tree.right.left = BinaryTreeNode(101)
tree.right.right = BinaryTreeNode(190)
tree.left.left = BinaryTreeNode(70)
check_bst(tree)


    

    




node 100, minv -inf, maxv inf
right? True, left? True, node 100, min -inf, max inf
node 80, minv -inf, maxv 100
right? True, left? True, node 80, min -inf, max 100
node 70, minv -inf, maxv 80
right? True, left? True, node 70, min -inf, max 80
node 105, minv 100, maxv inf
right? True, left? True, node 105, min 100, max inf
node 101, minv 100, maxv 105
right? True, left? True, node 101, min 100, max 105
node 190, minv 105, maxv inf
right? True, left? True, node 190, min 105, max inf






    
Out[34]:





True

In [35]:

    

tree.left.right = BinaryTreeNode(120)
check_bst(tree)


    

    




node 100, minv -inf, maxv inf
right? True, left? True, node 100, min -inf, max inf
node 80, minv -inf, maxv 100
right? False, left? True, node 80, min -inf, max 100






    
Out[35]:





False

In [36]:

    

tree.left.right = None
tree.right.left = BinaryTreeNode(99)
check_bst(tree)


    

    




node 100, minv -inf, maxv inf
right? True, left? True, node 100, min -inf, max inf
node 80, minv -inf, maxv 100
right? True, left? True, node 80, min -inf, max 100
node 70, minv -inf, maxv 80
right? True, left? True, node 70, min -inf, max 80
node 105, minv 100, maxv inf
right? True, left? False, node 105, min 100, max inf






    
Out[36]:





False

In [ ]: