Given the root of a binary tree. Check whether it is a BST or not.
Note: We are considering that BSTs can not contain duplicate Nodes.
A BST is defined as follows:
	
	The left subtree of a node contains only nodes with keys less than the node's key.
	
	
	The right subtree of a node contains only nodes with keys greater than the node's key.
	
	
	Both the left and right subtrees must also be binary search trees.
	
 
Example 1:
Input:
   2
 /    \
1      3
Output: 1 
Explanation: 
The left subtree of root node contains node
with key lesser than the root nodes key and 
the right subtree of root node contains node 
with key greater than the root nodes key.
Hence, the tree is a BST.
Example 2:
Input:
  2
   \
    7
     \
      6
       \
        5
         \
          9
           \
            2
             \
              6
Output: 0 
Explanation: 
Since the node with value 7 has right subtree 
nodes with keys less than 7, this is not a BST.
Your Task:
You don't need to read input or print anything. Your task is to complete the function isBST() which takes the root of the tree as a parameter and returns true if the given binary tree is BST, else returns false. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the BST).
Constraints:
0 <= Number of edges <= 100000

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Range queries

Starter code: #User function Template for python3





class Solution:

    

    #Function to check whether a Binary Tree is BST or not.

    def isBST(self, root):

        #code here





Solutions:
class Solution:

	def isBST(self, root):

		def bst(lower, upper, node):
			if not node:
				return True
			elif node.data <= lower or node.data >= upper:
				return False
			else:
				return bst(lower, node.data, node.left) and bst(node.data, upper, node.right)
		return bst(float('-inf'), float('inf'), root)


class Solution:

	def isBST(self, root):

		def solve(root, min, max):
			if root == None:
				return True
			return root.data < max and root.data > min and solve(root.left, min, root.data) and solve(root.right, root.data, max)
		return solve(root, -99999, 99999)


class Solution:

	def isBST(self, root):
		arr = []

		def in_order(node):
			if not node:
				return
			in_order(node.left)
			arr.append(node.data)
			in_order(node.right)
		in_order(root)
		return arr == sorted(arr) and len(set(arr)) == len(arr)


class Solution:

	def isBST(self, root):
		arr = []

		def pre_order(node):
			if not node:
				return
			pre_order(node.left)
			arr.append(node.data)
			pre_order(node.right)
		pre_order(root)
		for i in range(len(arr) - 1):
			if arr[i + 1] <= arr[i]:
				return False
		return True


class Solution:

	def isBSTUtil(self, node, min_value, max_value):
		if node is None:
			return True
		if node.data <= min_value or node.data >= max_value:
			return False
		return self.isBSTUtil(node.left, min_value, node.data) and self.isBSTUtil(node.right, node.data, max_value)

	def isBST(self, root):
		return self.isBSTUtil(root, float('-inf'), float('inf'))


class Solution:

	def isBST(self, root):
		stack = []
		prev_val = float('-inf')
		while root or stack:
			while root:
				stack.append(root)
				root = root.left
			node = stack.pop()
			if node.data <= prev_val:
				return False
			prev_val = node.data
			root = node.right
		return True


class Solution:

	def isBST(self, root):

		def isBSTUtil(node, mini, maxi):
			if node is None:
				return True
			if node.data <= mini or node.data >= maxi:
				return False
			return isBSTUtil(node.left, mini, node.data) and isBSTUtil(node.right, node.data, maxi)
		return isBSTUtil(root, -999999999, 999999999)


class Solution:

	def isBST(self, root, min_val=float('-inf'), max_val=float('inf')):
		if root is None:
			return True
		if not min_val < root.data < max_val:
			return False
		return self.isBST(root.left, min_val, root.data) and self.isBST(root.right, root.data, max_val)


class Solution:

	def isBST(self, root):

		def checkBST(root, max_val, min_val):
			if root == None:
				return True
			elif root.data >= max_val or root.data <= min_val:
				return False
			return checkBST(root.left, root.data, min_val) and checkBST(root.right, max_val, root.data)
		return checkBST(root, float('inf'), float('-inf'))


INT_MAX = 4294967296
INT_MIN = -4294967296

class Solution:

	def isBST(self, node):
		return self.isBSTUtil(node, INT_MIN, 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)


class Solution:

	def inorder(self, root, ans):
		if root == None:
			return
		self.inorder(root.left, ans)
		ans.append(root.data)
		self.inorder(root.right, ans)
		return ans

	def isBST(self, root):
		ans = []
		res = self.inorder(root, ans)
		for i in range(len(res) - 1):
			if res[i] >= res[i + 1]:
				return 0
		else:
			return 1


class Solution:

	def isBST(self, root):
		return self._isBst(root, -10000000, 10000000)

	def _isBst(self, node, min_value, max_value):
		if not node:
			return True
		if node.data < min_value or node.data > max_value:
			return False
		return self._isBst(node.left, min_value, node.data - 1) and self._isBst(node.right, node.data - 1, max_value)


class Solution:

	def solve(self, root, l, r):
		if root is None:
			return True
		if not (root.data > l and root.data < r):
			return False
		x = self.solve(root.left, l, root.data)
		y = self.solve(root.right, root.data, r)
		return x and y

	def isBST(self, root):
		LIMIT = 100000
		return self.solve(root, -1, LIMIT)


class Solution:

	def isBST(self, root):

		def inorder(root):
			if root is None:
				return []
			left = inorder(root.left)
			left.append(root.data)
			right = inorder(root.right)
			return left + right
		values = inorder(root)
		for i in range(1, len(values)):
			if values[i] <= values[i - 1]:
				return False
		return True


class Solution:

	def solve(self, root, prev):
		if root == None:
			return True
		if not self.solve(root.left, prev):
			return False
		if prev[0] != None and root.data <= prev[0].data:
			return False
		prev[0] = root
		return self.solve(root.right, prev)

	def isBST(self, root):
		prev = [None]
		return self.solve(root, prev)


class Solution:

	def isBST(self, root):

		def checker(root, min_val, max_val):
			if root is None:
				return True
			if root.data < min_val or root.data > max_val:
				return False
			return checker(root.left, min_val, root.data - 1) and checker(root.right, root.data + 1, max_val)
		return checker(root, float('-inf'), float('inf'))


class Solution:

	def isBST(self, root):
		if root == None:
			return True
		stack = []
		prev = None
		while stack or root:
			while root:
				stack.append(root)
				root = root.left
			root = stack.pop()
			if prev != None and root.data <= prev.data:
				return False
			prev = root
			root = root.right
		return True


class Solution:

	def isBST(self, root):

		def valid(node, left, right):
			if not node:
				return True
			if not (node.data > left and node.data < right):
				return False
			return valid(node.left, left, node.data) and valid(node.right, node.data, right)
		return valid(root, float('-inf'), float('inf'))


class Solution:

	def inOrderTraversal(root):
		if root == None or root.left == None or root.right == None:
			return []
		ans = []
		ans = ans + inOrderTraversal(root.left) + [root.data] + inOrderTraversal(root.right)
		return ans

	def isBST(self, root):
		sortedData = []
		current = root
		stack = []
		while True:
			if current is not None:
				stack.append(current)
				current = current.left
			elif len(stack) > 0:
				current = stack.pop()
				sortedData.append(current.data)
				current = current.right
			else:
				break
		for i in range(1, len(sortedData) - 1):
			if sortedData[i - 1] >= sortedData[i] or sortedData[i] >= sortedData[i + 1]:
				return False
		return True


import math

class Solution:

	def __init__(self):
		self.prev = -math.inf

	def isBST(self, root):
		if root is None:
			return True
		if not self.isBST(root.left):
			return False
		if root.data <= self.prev:
			return False
		self.prev = root.data
		return self.isBST(root.right)


import math

class Solution:

	def isBST(self, root, mn=-math.inf, mx=math.inf):
		if root is None:
			return True
		return root.data > mn and root.data < mx and self.isBST(root.left, mn, root.data) and self.isBST(root.right, root.data, mx)


class Solution:

	def isBST(self, root):
		stack = [(root, False)]
		ans = 0
		while stack:
			(node, visited) = stack.pop()
			if visited:
				if ans < node.data:
					ans = node.data
				else:
					return 0
			elif node:
				stack.append((node.right, False))
				stack.append((node, True))
				stack.append((node.left, False))
		return 1


class Solution:

	def minimum(self, root):
		if root is None:
			return 100000
		left_sub = self.minimum(root.left)
		right_sub = self.minimum(root.right)
		return min(root.data, left_sub, right_sub)

	def maximum(self, root):
		if root is None:
			return -100000
		left_sub = self.maximum(root.left)
		right_sub = self.maximum(root.right)
		return max(root.data, left_sub, right_sub)

	def isBST(self, root):
		if root is None:
			return True
		if root.data <= self.maximum(root.left) or root.data > self.minimum(root.right):
			return False
		return self.isBST(root.left) and self.isBST(root.right)


class Solution:

	def isBST(self, root):

		def inOrderTraversal(root):
			result = []
			if root.left is not None:
				result.extend(inOrderTraversal(root.left))
			result.append(root.data)
			if root.right is not None:
				result.extend(inOrderTraversal(root.right))
			return result
		result = inOrderTraversal(root)
		i = 1
		while i < len(result):
			if result[i - 1] >= result[i]:
				return False
			i += 1
		return True


class Solution:

	def isBST(self, root):

		def inorder(root, lower=float('-inf'), upper=float('inf')):
			if root is None:
				return True
			if root.data <= lower or root.data >= upper:
				return False
			if not inorder(root.left, lower, root.data):
				return False
			if not inorder(root.right, root.data, upper):
				return False
			return True
		return inorder(root)


def func(root, ans):
	if root is None:
		return
	func(root.left, ans)
	ans.append(root.data)
	func(root.right, ans)

class Solution:

	def isBST(self, root):
		ans = []
		func(root, ans)
		return all((ans[i] < ans[i + 1] for i in range(len(ans) - 1)))


class Solution:

	def __init__(self):
		self.prev = float('-inf')

	def isBST(self, root):
		if not root:
			return True
		if not self.isBST(root.left):
			return False
		if root.data <= self.prev:
			return False
		self.prev = root.data
		return self.isBST(root.right)


class Solution:

	def _isbst(self, root, minn, maxx):
		if root is None:
			return True
		if root.data > minn and root.data < maxx:
			left = self._isbst(root.left, minn, root.data)
			right = self._isbst(root.right, root.data, maxx)
			return left and right
		else:
			return False

	def isBST(self, root):
		return self._isbst(root, float('-inf'), float('inf'))


class Solution:

	def isBST(self, root):
		if root is None:
			return True
		stack = []
		current = root
		result = []
		while current or stack:
			while current:
				stack.append(current)
				current = current.left
			current = stack.pop()
			result.append(current.data)
			current = current.right
		i = 1
		while i < len(result):
			if not result[i - 1] < result[i]:
				return False
			i += 1
		return True


class Solution:

	def isBST(self, root):
		if not hasattr(self, 'lastmax'):
			self.lastmax = -float('inf')
		if root is None:
			return True
		left = self.isBST(root.left)
		if left == False:
			return False
		if self.lastmax >= root.data:
			return False
		self.lastmax = root.data
		return self.isBST(root.right)


import sys

class Solution:

	def isBST(self, root):

		def isBSTUtil(node, mini, maxi):
			if node is None:
				return 1
			if node.data < mini or node.data > maxi:
				return 0
			return isBSTUtil(node.left, mini, node.data - 1) and isBSTUtil(node.right, node.data + 1, maxi)
		minINT = -sys.maxsize + 1
		maxINT = sys.maxsize
		return isBSTUtil(root, minINT, maxINT)


class Solution:

	def isBST(self, root):

		def BST(root, left_bound, right_bound):
			if root != None:
				l = BST(root.left, left_bound, root.data)
				r = BST(root.right, root.data, right_bound)
				if left_bound < root.data <= right_bound:
					if root.left and root.data <= root.left.data:
						rl = False
					else:
						rl = True
					if root.right and root.data > root.right.data:
						rr = False
					else:
						rr = True
				else:
					rl = False
					ll = False
				return l and r and (rl and rr)
			return True
		return BST(root, float('-inf'), float('inf'))


class Solution:
	maxi = 100000
	mini = 0

	def isBST(self, root):
		return self.check_BST(root, self.mini, self.maxi)

	def check_BST(self, root, mini, maxi):
		if root == None:
			return True
		if root.data < mini or root.data > maxi:
			return False
		return self.check_BST(root.left, mini, root.data - 1) and self.check_BST(root.right, root.data + 1, maxi)


class Solution:

	def isBST1(self, root):
		q = root
		a = True
		if not root:
			return True
		print('--' + str(root.data))
		if q.left:
			print('left ' + str(q.left.data))
		if q.right:
			print('right ' + str(q.right.data))
		if q.left and root.data <= q.left.data:
			return False
		elif q.right and root.data >= q.right.data:
			return False
		else:
			if a and root.left:
				a = self.isBST(q.left)
			if a and root.right:
				a = self.isBST(q.right)
			return a

	def f(self, root, a, b):
		if not root:
			return True
		if root.data <= a or root.data >= b:
			return False
		t = self.f(root.left, a, root.data)
		m = self.f(root.right, root.data, b)
		return t and m

	def isBST(self, root):
		return self.f(root, 0, 100000)


class Solution:

	def isBST(self, root):

		def isBSTUtil(root, max, min):
			if not root:
				return True
			if root.data >= max:
				return False
			if root.data <= min:
				return False
			return isBSTUtil(root.left, root.data, min) and isBSTUtil(root.right, max, root.data)
		INT_MAX = 4294967296
		INT_MIN = -4294967296
		return isBSTUtil(root, INT_MAX, INT_MIN)


class Solution:

	def isBST(self, root):
		self.curr = None

		def helper(root):
			if root is None:
				return True
			left = helper(root.left)
			if self.curr and self.curr.data >= root.data:
				return False
			else:
				self.curr = root
			right = helper(root.right)
			return left and right
		return helper(root)


class Solution:

	def isBST(self, root):

		def helper(root, left=-99999999, right=99999999):
			if not root:
				return True
			return left < root.data < right and helper(root.left, left, root.data) and helper(root.right, root.data, right)
		return helper(root)


class Solution:

	def isBST(self, root):
		self.ordered_array = []

		def _in_order_traversal(node):
			if not node:
				return
			_in_order_traversal(node.left)
			self.ordered_array.append(node.data)
			_in_order_traversal(node.right)

		def _check_bst(array):
			for i in range(1, len(array)):
				if array[i] <= array[i - 1]:
					return 0
			return 1
		_in_order_traversal(root)
		return _check_bst(self.ordered_array)


class Solution:

	def inorder(self, root, mylist):
		if root is None:
			return
		self.inorder(root.left, mylist)
		mylist.append(root.data)
		self.inorder(root.right, mylist)

	def isBST(self, root):
		mylist = []
		self.inorder(root, mylist)
		for i in range(1, len(mylist)):
			if mylist[i - 1] < mylist[i]:
				continue
			else:
				return 0
		return 1


class Solution:

	def check(self, root, minval, maxval):
		if root is None:
			return True
		if root.data > maxval or root.data < minval:
			return False
		return self.check(root.left, minval, root.data - 1) and self.check(root.right, root.data + 1, maxval)

	def isBST(self, root):
		minval = (2 ** 64 - 1) * -1
		maxval = 2 ** 64 - 1
		return self.check(root, minval, maxval)


import sys

class Solution:
	prev = -1

	def inorder(self, root):
		if root == None:
			return True
		if root:
			if not self.inorder(root.left):
				return False
			if self.prev >= root.data:
				return False
			self.prev = root.data
			if not self.inorder(root.right):
				return False
		return True

	def isBST(self, root):
		return self.inorder(root)


class Solution:

	def isBST(self, root):
		return self.isBSTHelper(root, float('-inf'), float('inf'))

	def isBSTHelper(self, node, minVal, maxVal):
		if node is None:
			return True
		if node.data <= minVal or node.data >= maxVal:
			return False
		return self.isBSTHelper(node.left, minVal, node.data) and self.isBSTHelper(node.right, node.data, maxVal)


class Solution:

	def inorder(self, root, res):
		if root:
			self.inorder(root.left, res)
			res.append(root.data)
			self.inorder(root.right, res)

	def isBST(self, root):
		res = []
		self.inorder(root, res)
		for i in range(1, len(res)):
			if res[i] <= res[i - 1]:
				return False
		return True


class Solution:

	def isBST(self, root):

		def isBSTUtil(root, min, max):
			if root:
				if root.left:
					if root.left.data >= root.data or root.left.data < min:
						return 0
				if root.right:
					if root.right.data <= root.data or root.right.data > max:
						return 0
				return 1 if isBSTUtil(root.left, min, root.data) == 1 and isBSTUtil(root.right, root.data, max) == 1 else 0
			else:
				return 1
		return isBSTUtil(root, 0, 100000)


class Solution:

	def getIno(self, root, li):
		if root:
			self.getIno(root.left, li)
			li.append(root.data)
			self.getIno(root.right, li)

	def isBST(self, root):
		if root:
			li = []
			self.getIno(root, li)
			for i in range(len(li) - 1):
				if li[i] >= li[i + 1]:
					return False
			return True
		else:
			return True


class Solution:

	def isBST(self, root, min_val=float('-inf'), max_val=float('inf')):
		if not root:
			return True
		if root.data <= min_val or root.data >= max_val:
			return False
		left_subtree_is_bst = self.isBST(root.left, min_val, root.data)
		right_subtree_is_bst = self.isBST(root.right, root.data, max_val)
		return left_subtree_is_bst and right_subtree_is_bst


class Solution:

	def inorder(self, root, r):
		if not root:
			return True
		if root.data not in range(r[0], r[1]):
			return False
		l = self.inorder(root.left, [r[0], root.data])
		r = self.inorder(root.right, [root.data, r[1]])
		return l and r

	def isBST(self, root):
		r = [int(-1 * (1000000000.0 + 7)), int(1000000000.0 + 7)]
		return self.inorder(root, r)


class Solution:

	def inoder(self, root, limts):
		if not root:
			return True
		if root.data not in range(limts[0], limts[1]):
			return False
		leftSol = self.inoder(root.left, [limts[0], root.data])
		rightSol = self.inoder(root.right, [root.data, limts[1]])
		return leftSol and rightSol

	def isBST(self, root):
		r = [int(-1 * (1000000000.0 + 7)), int(1000000000.0 + 7)]
		return self.inoder(root, r)


from sys import maxsize

class Solution:

	def isBST(self, root):

		def checkBST(root, low, high):
			if root is None:
				return True
			if root.data <= low or root.data >= high:
				return False
			return checkBST(root.left, low, root.data) and checkBST(root.right, root.data, high)
		return checkBST(root, -maxsize, maxsize)


prev = None

def f(root):
	if root:
		if not f(root.left):
			return False
		global prev
		if prev >= root.data:
			return False
		prev = root.data
		if not f(root.right):
			return False
	return True

class Solution:

	def isBST(self, root):
		global prev
		prev = -(2 << 31 + 1)
		return True if f(root) else 0


class Solution:

	def isBST(self, root):

		def checkbst(root, lst):
			if root == None:
				return
			checkbst(root.left, lst)
			lst.append(root.data)
			checkbst(root.right, lst)
		lst = []
		checkbst(root, lst)
		for i in range(1, len(lst)):
			if lst[i - 1] >= lst[i]:
				return 0
				break
		return 1


import math

class Solution:

	def isBST(self, root):
		return self.check(root, -math.inf, math.inf)

	def check(self, root, minval, maxval):
		if not root:
			return True
		if root.data <= minval or root.data >= maxval:
			return False
		return self.check(root.left, minval, root.data) and self.check(root.right, root.data, maxval)


class Solution:

	def inorder(self, root, arr):
		if root is not None:
			self.inorder(root.left, arr)
			arr.append(root.data)
			self.inorder(root.right, arr)

	def isBST(self, root):
		arr = []
		self.inorder(root, arr)
		for i in range(len(arr) - 1):
			if arr[i] >= arr[i + 1]:
				return 0
		return 1


class Solution:

	def isBST(self, root):
		return self.bst(root)[0]

	def bst(self, root):
		if root is None:
			return (True, float('inf'), float('-inf'))
		(left_is_bst, left_min, left_max) = self.bst(root.left)
		(right_is_bst, right_min, right_max) = self.bst(root.right)
		if left_is_bst and right_is_bst and (left_max < root.data < right_min):
			return (True, min(left_min, root.data), max(right_max, root.data))
		else:
			return (False, 0, 0)


class Solution:

	def isBST(self, root):
		ans = 1
		li = []

		def inOrder(root):
			if root == None:
				return []
			inOrder(root.left)
			li.append(root.data)
			inOrder(root.right)
		inOrder(root)
		for i in range(1, len(li)):
			if li[i - 1] >= li[i]:
				ans = 0
				break
		return ans


class Solution:

	def isBST(self, root):
		prev = None
		curr = root
		pred = None
		while curr is not None:
			if not curr.left:
				if prev and prev.data >= curr.data:
					return False
				prev = curr
				curr = curr.right
			else:
				pred = curr.left
				while pred.right and pred.right != curr:
					pred = pred.right
				if not pred.right:
					pred.right = curr
					curr = curr.left
				else:
					if prev and prev.data >= curr.data:
						return False
					prev = curr
					curr = pred.right.right
					pred.right = None
		return True


import sys

def solve(self, root, mn, mx):
	if root == None:
		return 1
	if root.data <= mn or root.data >= mx:
		return False
	return solve(self, root.left, mn, root.data) and solve(self, root.right, root.data, mx)

class Solution:

	def isBST(self, root):
		mx = sys.maxsize
		mn = -sys.maxsize - 1
		return solve(self, root, mn, mx)


from math import inf

class Solution:

	def isBST(self, root, left=-inf, right=inf):
		if not root:
			return 1
		if root.data <= left or root.data >= right:
			return 0
		return self.isBST(root.left, left, root.data) and self.isBST(root.right, root.data, right)


class Solution:

	def maxValue(self, node):
		if node is None:
			return 0
		leftMax = self.maxValue(node.left)
		rightMax = self.maxValue(node.right)
		value = 0
		if leftMax > rightMax:
			value = leftMax
		else:
			value = rightMax
		if value < node.data:
			value = node.data
		return value

	def minValue(self, node):
		if node is None:
			return 1000000000
		leftMax = self.minValue(node.left)
		rightMax = self.minValue(node.right)
		value = 0
		if leftMax < rightMax:
			value = leftMax
		else:
			value = rightMax
		if value > node.data:
			value = node.data
		return value

	def isBST(self, node):
		if node is None:
			return 1
		if node.left is not None and self.maxValue(node.left) >= node.data:
			return 0
		if node.right is not None and self.minValue(node.right) <= node.data:
			return 0
		if self.isBST(node.left) is 0 or self.isBST(node.right) is 0:
			return 0
		return 1


class Solution:

	def is_bst_helper(self, node, min_val, max_val):
		if node is None:
			return True
		if node.data <= min_val or node.data >= max_val:
			return False
		return self.is_bst_helper(node.left, min_val, node.data) and self.is_bst_helper(node.right, node.data, max_val)

	def isBST(self, root):
		return self.is_bst_helper(root, float('-inf'), float('inf'))


import sys

class Solution:

	def helper(self, node, low, high):
		if not node:
			return True
		if not low < node.data < high:
			return False
		return self.helper(node.left, low, node.data) and self.helper(node.right, node.data, high)

	def isBST(self, root):
		prev = None
		return self.helper(root, -sys.maxsize - 1, sys.maxsize)


INT_MAX = 4294967296
INT_MIN = -4294967296

def isValid(root, minm, maxm):
	if not root:
		return True
	if root.data < minm or root.data > maxm:
		return False
	return isValid(root.left, minm, root.data - 1) and isValid(root.right, root.data + 1, maxm)

class Solution:

	def isBST(self, root):
		return isValid(root, INT_MIN, INT_MAX)


from sys import maxsize

class Solution:

	def isBST(self, root, mini=-maxsize, maxi=maxsize):
		if root is None:
			return True
		if mini < root.data < maxi:
			is_left_bst = self.isBST(root.left, mini, root.data)
			is_right_bst = self.isBST(root.right, root.data, maxi)
			return is_left_bst and is_right_bst
		return False


class Solution:

	def isBST(self, root):

		def check(minv, maxv, n):
			if not n:
				return True
			return minv < n.data < maxv and check(minv, n.data, n.left) and check(n.data, maxv, n.right)
		return check(float('-inf'), float('inf'), root)


class Solution:

	def bst(self, root, mini, maxi):
		if root is None:
			return True
		if root.data < mini or root.data > maxi:
			return False
		return self.bst(root.left, mini, root.data - 1) and self.bst(root.right, root.data + 1, maxi)

	def isBST(self, root):
		mini = -4294967296
		maxi = 4294967296
		return self.bst(root, mini, maxi)


class Solution:

	def isBST(self, root):
		arr = []

		def inorder(root):
			if root is None:
				return None
			inorder(root.left)
			arr.append(root.data)
			inorder(root.right)
		inorder(root)
		b = arr.copy()
		b = list(set(b))
		b.sort()
		if b == arr:
			return 1
		else:
			return 0


class Solution:

	def isBST(self, root):

		def is_bst(root):
			if root is None:
				return (True, None, None)
			(is_bst_l, min_l, max_l) = is_bst(root.left)
			(is_bst_r, min_r, max_r) = is_bst(root.right)
			is_bst_node = is_bst_l and is_bst_r and (max_l is None or root.data > max_l) and (min_r is None or root.data < min_r)
			min_key = min([x for x in [min_l, root.data, min_r] if x is not None])
			max_key = max([x for x in [min_l, root.data, max_r] if x is not None])
			return (is_bst_node, min_key, max_key)
		(t, _, _) = is_bst(root)
		return t


class Solution:

	def isBST(self, root):
		return self._isBST(root, 9999999999999, -9999999999999999)

	def _isBST(self, node, max, min):
		if node is None:
			return True
		if node.data >= max or node.data <= min:
			return False
		return self._isBST(node.left, node.data, min) and self._isBST(node.right, max, node.data)


class Solution:

	def isBST(self, root):

		def helper(node, lower=float('-inf'), upper=float('inf')):
			if not node:
				return True
			val = node.data
			if val <= lower or val >= upper:
				return False
			if not helper(node.right, val, upper):
				return False
			if not helper(node.left, lower, val):
				return False
			return True
		return helper(root)


class Solution:

	def isBST(self, root):
		l = []

		def in_order(root):
			if root.left != None:
				in_order(root.left)
			l.append(root.data)
			if root.right != None:
				in_order(root.right)
		in_order(root)
		if l == sorted(l) and len(l) == len(set(l)):
			return 1
		else:
			return 0