We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Practice
  2. Tutorials
  3. Cracking the Coding Interview
  4. Trees: Is This a Binary Search Tree?
  5. Discussions

Trees: Is This a Binary Search Tree?

  • witygass + 0 comments

    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