Check for BST or Not

In this class, We discuss Check for BST or Not.

Readers can prepare a full competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given a binary tree with no duplicate keys.

Our task is to find whether the given binary tree is a binary search tree.

BST Conditions:

The element in the left subtree is smaller

The element in the right subtree is larger.

The above conditions should be satisfied for all the nodes.

The below diagram shows the input and output examples.

Logic:

The first point that comes to our mind is whether we need to check for a binary search tree.

Take each node and check the condition that the left element should be less and the right element should be greater.

But this simple logic will only work in some situations.

In the Binary search tree, the left sub-tree should contain fewer elements, and the right subtree should have greater ones.

We must maintain minimum and maximum values to check for the entire subtree.

To check all the nodes, we use a recursive function call.

Each function call will maintain the minimum and maximum value required for its subtree.

The step-by-step understanding is provided in the video.

Code:

class Node:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right=None

class Solution:

    INT_MAX = 4294967296

    INT_MIN = -4294967296

    def isBST(self, root):

        return (self.isBSTUtil(root, Solution.INT_MIN, Solution.INT_MAX))

    def isBSTUtil(self,node, mini, maxi):

        if node is None:

            return True

        if node.data < mini or node.data > maxi:

            return False

        return (self.isBSTUtil(node.left, mini, node.data – 1) and \

        self.isBSTUtil(node.right, node.data+1, maxi))

ob=Node(10)

ob1=Node(5)

ob2=Node(12)

ob3=Node(2)

ob4=Node(9)

ob5=Node(11)

ob6=Node(14)

ob.left=ob1

ob.right=ob2

ob1.left=ob3

ob1.right=ob4

ob2.left=ob5

ob2.right=ob6

head=ob

obj=Solution()

k=obj.isBST(head)

print(k)