Question

Write a method for binary tree in Python that can determine whether a binary tree is a binary search tree or not. The input should be a binary tree. The output should be true or false. True= binary tree meets the criteria to be a binary search tree. False= does not meet the criteria to be a binary search tree.

Answer 1

NOTE:If you are stuck somewhere feel free to ask in the comments i will be happy to guide you through this but do not give negative rating o the question as it affects my answering rights..........

Also note i have made a binary tree impilcity for checking if the code works or not....You can ask the user to make a binary tree...by just adding a insert function here and asking to add values from user

INT_MAX = 4294967296
INT_MIN = -4294967296

# A binary tree node 
class Node: 

        #this is the constructor to initialise the new node with initial values
        def __init__(self, data): 
                self.data = data 
                self.left = None
                self.right = None



def isBST(node): 
        return (isBSTUtil(node, INT_MIN, INT_MAX)) 

 
def isBSTUtil(node, mini, maxi): 
        
        # An empty tree is BST 
        if node is None: 
                return True

        # False if this node violates 
    #left child should be less than parent node and right child should be greater than current node
    #here we keep a track on that by maintaining a max and min value
    #is the current node is less than minimum or greater than maximum then it is not BST 
        if node.data < mini or node.data > maxi: 
                return False

        return (isBSTUtil(node.left, mini, node.data -1) and
                isBSTUtil(node.right, node.data+1, maxi)) #now recur check for the left AND the right child

#code to test above function 
root = Node(6) 
root.left = Node(2) 
root.right = Node(7) 
root.left.left = Node(1) 
root.left.right = Node(3) 

if (isBST(root)): 
        print ("The Binary tree is a BST")
else: 
        print ("The Binary tree is not a BST")

Output:-->