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)