@@ -0,0 +1,1423 @@
+%22%22%22%0AWrite a program to check if a given binary tree is bst or not.%0A%22%22%22%0A%0A%22%22%22%0AApproach 1:%0A1. For each node, check that node's value is greater than max_value in its left subtree and smaller than%0A   min_value in its right subtree.%0A2. This approach is not efficient as each node is traversed multiple times.%0A%0AApproach 2:%0A1. We use two variables, min and max, to track the range in which the current node's data should lie.%0A2. Initially, min = -INF and max = INF.%0A3. At each node, when we go to its left subtree, we make max = node.data and when we go to its right subtree%0A   we make min = node.data%0A%0AApproach 3:%0A1. We can do an in-order traversal of the tree and see if the output is sorted.%0A2. A space optimization is, we only keep track of previously seen node's value. If current node's value%0A   is less than previous node's value, binary tree is not BST.%0A%0ABelow, Approach 2 is implemented.%0A%22%22%22%0A%0A%0Aclass Node:%0A    def __init__(self, data, left=None, right=None):%0A        self.data = data%0A        self.left = left%0A        self.right = right%0A%0A%0Adef is_bst(node):%0A    if node is None:%0A        return True%0A    return is_bst_helper(node, -float('inf'), float('inf'))%0A%0A%0Adef is_bst_helper(node, min_val, max_val):%0A    if node is None:%0A        return True%0A    if node.data %3C min_val or node.data %3E max_val:%0A        return False%0A    return is_bst_helper(node.left, min_val, node.data) and is_bst_helper(node.right, node.data, max_val)%0A

Check if binary tree is a BST