This comment was a lifesaver for me.. I was really struggling to find a way to do this in linear time / constant space. I took your advice with the inorder traversal and used a single closure variable to store the last value visited instead of a list. I think that lead to a pretty concise solution. Thanks!

lastVal = [None]

def check_binary_search_tree_(root):
  if not root: return True
  left = check_binary_search_tree_(root.left)
  if root.data <= lastVal[0]: return False
  lastVal[0] = root.data
  right = check_binary_search_tree_(root.right)
  return left and right