Is This a Binary Search Tree?

  • + 0 comments
    """ Node is defined as
    class node:
      def __init__(self, data):
          self.data = data
          self.left = None
          self.right = None
    """
    
    # Could've used inorder traversal and, every time a node is added to results array, check if it's actually greater than the value prior to it, but decided to use try this approach instead, lol.
    
    def check_binary_search_tree_(root):
        # node, min val in current range, max val in current range. Range updates every time a new node is visited. Given the range values, I can implicitly tell whether I'm moving either to the left or to the right.
        stack = [(root, 0, 10e4)]
    
        while stack:
            current, min_in_range, max_in_range = stack.pop()
            if not (min_in_range < current.data < max_in_range):
                return False
    
            if current.right:
                stack.append((current.right, current.data, max_in_range))
            if current.left:
                stack.append((current.left, min_in_range, current.data))
    
        return True