gistfile1.py

class Node:
    def __init__(self,val):
        self.val = val
        self.left = None
        self.right = None

    def __cmp__(self, other):
        return cmp(self.val, other.val)
    
    def valid(self, side):
        if self.left and not self.left < self: return False
        if self.right and not self.right > self: return False
        if self.right and self.left and not self.left < self.right: return False
        if self.left:
            ok, l = self.valid(False)
            if not ok and not l < self.value: return False
        if self.right:
            ok, r = self.valid(True)
            if not ok and not self.value > r: return False
        if side:
           # right
           if self.right:
               val = self.right.val
           else:
               val = self.val
        else: #left
           if self.left:
               val = self.left.val
           else:
               val = self.val
        return  True, val


def validateBST(node):
    ok, _ = node.valid(True):
    return ok