Given a binary tree. Find the size of its largest subtree that is a Binary Search Tree.
Note: Here Size is equal to the number of nodes in the subtree.
Example 1:
Input:
        1
      /   \
     4     4
   /   \
  6     8
Output: 1
Explanation: There's no sub-tree with size
greater than 1 which forms a BST. All the
leaf Nodes are the BSTs with size equal
to 1.
Example 2:
Input: 6 6 3 N 2 9 3 N 8 8 2
            6
        /       \
       6         3
        \      /   \
         2    9     3
          \  /  \
          8 8    2 
Output: 2
Explanation: The following sub-tree is a
BST of size 2: 
       2
    /    \ 
   N      8
Your Task:
You don't need to read input or print anything. Your task is to complete the function largestBst() that takes the root node of the Binary Tree as its input and returns the size of the largest subtree which is also the BST. If the complete Binary Tree is a BST, return the size of the complete Binary Tree. 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(Height of the BST).
Constraints:
1 ≤ Number of nodes ≤ 10^{5}
1 ≤ Data of a node ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Sorting

Data structures

Range queries

Starter code: #User function Template for python3

class Solution:
    # Return the size of the largest sub-tree which is also a BST
    def largestBst(self, root):
        #code here

Solutions:
class Solution:

	def check(self, root, result):
		if root == None:
			return ['n', 'n']
		(a1, b1) = self.check(root.left, result)
		(a2, b2) = self.check(root.right, result)
		if a1 == 'f' and b1 == 'f' or (a2 == 'f' and b2 == 'f'):
			return ['f', 'f']
		if a1 == 'n' and b1 == 'n' and (a2 == 'n') and (b2 == 'n'):
			a1 = root.data
			b1 = root.data
			a2 = root.data
			b2 = root.data
			result.append(root)
			return (a1, b2)
		elif a1 == 'n' and b1 == 'n':
			a1 = root.data
			b1 = root.data
			if a2 <= root.data:
				return ['f', 'f']
			else:
				result.append(root)
				return (a1, b2)
		elif a2 == 'n' and b2 == 'n':
			a2 = root.data
			b2 = root.data
			if b1 >= root.data:
				return ['f', 'f']
			else:
				result.append(root)
				return (a1, b2)
		elif a2 <= root.data or b1 >= root.data:
			return ['f', 'f']
		else:
			result.append(root)
			return (a1, b2)

	def cal_size(self, root):
		if root == None:
			return 0
		lh = self.cal_size(root.left)
		rh = self.cal_size(root.right)
		return lh + rh + 1

	def largestBst(self, root):
		result = []
		a = self.check(root, result)
		size = 0
		for i in result:
			temp = self.cal_size(i)
			if temp > size:
				size = temp
		return size


class Solution:

	def largestBst(self, root):

		def solve(root):
			if not root:
				return (True, float('-inf'), float('inf'), 0)
			(lbst, lmax, lmin, lcnt) = solve(root.left)
			(rbst, rmax, rmin, rcnt) = solve(root.right)
			if lbst and rbst and (lmax < root.data < rmin):
				return (True, max(root.data, rmax), min(root.data, lmin), 1 + lcnt + rcnt)
			else:
				return (False, 0, 0, max(lcnt, rcnt))
		return solve(root)[3]


class node:

	def __init__(self, mini, maxi, size):
		self.maxi = maxi
		self.mini = mini
		self.size = size

class Solution:

	def f(self, root):
		if root == None:
			return node(sys.maxsize, -sys.maxsize, 0)
		lt = self.f(root.left)
		rt = self.f(root.right)
		if lt.maxi < root.data and root.data < rt.mini:
			return node(min(root.data, lt.mini), max(root.data, rt.maxi), lt.size + rt.size + 1)
		return node(-sys.maxsize, sys.maxsize, max(lt.size, rt.size))

	def largestBst(self, root):
		a = self.f(root)
		return a.size


class Solution:

	def countnodes(self, root):
		if root == None:
			return 0
		ln = self.countnodes(root.left)
		rn = self.countnodes(root.right)
		return 1 + ln + rn

	def isbst(self, root, mini, maxi):
		if root == None:
			return True
		if mini < root.data and root.data < maxi:
			return self.isbst(root.left, mini, root.data) and self.isbst(root.right, root.data, maxi)
		else:
			return False

	def f(self, root, a):
		if root == None:
			return 0
		mini = -sys.maxsize
		maxi = sys.maxsize
		if self.isbst(root, mini, maxi):
			a[0] = max(a[0], self.countnodes(root))
		self.f(root.left, a)
		self.f(root.right, a)
		return a[0]

	def largestBst(self, root):
		a = [1]
		return self.f(root, a)


class Trio:

	def __init__(self, minNode, maxNode, maxSize):
		self.minNode = minNode
		self.maxNode = maxNode
		self.maxSize = maxSize

class Solution:

	def helper(self, root):
		if root == None:
			return Trio(float('inf'), float('-inf'), 0)
		left = self.helper(root.left)
		right = self.helper(root.right)
		if left.maxNode < root.data and root.data < right.minNode:
			return Trio(min(root.data, left.minNode), max(root.data, right.maxNode), left.maxSize + right.maxSize + 1)
		return Trio(float('-inf'), float('inf'), max(left.maxSize, right.maxSize))

	def largestBst(self, root):
		ans = self.helper(root)
		return ans.maxSize


class Solution:

	def largestBst(self, root):
		if not root:
			return 0
		elif self.checkIfBST(root, -float('inf'), float('inf')):
			return self.getSizeOfTree(root)
		else:
			return max(self.largestBst(root.left), self.largestBst(root.right))

	def getSizeOfTree(self, root):
		if not root:
			return 0
		else:
			return 1 + self.getSizeOfTree(root.left) + self.getSizeOfTree(root.right)

	def checkIfBST(self, root, lbound, rbound):
		if not root:
			return True
		else:
			return lbound < root.data < rbound and self.checkIfBST(root.left, lbound, root.data) and self.checkIfBST(root.right, root.data, rbound)


class Solution:

	def largestBst(self, root):

		def solve(root):
			if not root:
				return [0, -1000000000.0, 1000000000.0]
			if not root.left and (not root.right):
				return [1, root.data, root.data]
			l = solve(root.left)
			r = solve(root.right)
			if root.data > l[1] and root.data < r[2]:
				return [l[0] + r[0] + 1, max(root.data, r[1]), min(root.data, l[2])]
			else:
				return [max(l[0], r[0]), 1000000000.0, -1000000000.0]
		return solve(root)[0]


from sys import maxsize

class Answer:

	def __init__(self, maxi=-maxsize, mini=maxsize, is_bst=True, size=0):
		self.maxi = maxi
		self.mini = mini
		self.is_bst = is_bst
		self.size = size

class Solution:

	def solve(self, root):
		if root is None:
			return Answer()
		left = self.solve(root.left)
		right = self.solve(root.right)
		curr = Answer()
		curr.maxi = max(root.data, right.maxi)
		curr.mini = min(root.data, left.mini)
		if left.is_bst and right.is_bst and (left.maxi < root.data < right.mini):
			curr.is_bst = True
			curr.size = left.size + right.size + 1
		else:
			curr.is_bst = False
			curr.size = max(left.size, right.size)
		return curr

	def largestBst(self, root):
		ans = self.solve(root)
		return ans.size


class NodeValue:

	def __init__(self, minNode, maxNode, maxSize):
		self.maxNode = maxNode
		self.minNode = minNode
		self.maxSize = maxSize

class Solution:

	def largestBst(self, root):

		def LargestBST(root):
			if not root:
				return NodeValue(float('inf'), float('-inf'), 0)
			leftValue = LargestBST(root.left)
			rightValue = LargestBST(root.right)
			if leftValue.maxNode < root.data and root.data < rightValue.minNode:
				return NodeValue(min(leftValue.minNode, root.data), max(rightValue.maxNode, root.data), 1 + leftValue.maxSize + rightValue.maxSize)
			return NodeValue(float('-inf'), float('inf'), max(leftValue.maxSize, rightValue.maxSize))
		return LargestBST(root).maxSize


class NodeValue:

	def __init__(self, minNode, maxNode, maxSize):
		self.minNode = minNode
		self.maxNode = maxNode
		self.maxSize = maxSize

class Solution:

	def largestBst(self, root):

		def largestBSTHelper(root):
			if not root:
				return NodeValue(float('inf'), float('-inf'), 0)
			left = largestBSTHelper(root.left)
			right = largestBSTHelper(root.right)
			if left.maxNode < root.data < right.minNode:
				return NodeValue(min(root.data, left.minNode), max(root.data, right.maxNode), left.maxSize + right.maxSize + 1)
			return NodeValue(float('-inf'), float('inf'), max(left.maxSize, right.maxSize))
		return largestBSTHelper(root).maxSize


class help:

	def __init__(self, mini, maxi, size):
		self.mini = mini
		self.maxi = maxi
		self.size = size

class Solution:

	def isBst(self, root):
		if root is None:
			return help(float('inf'), float('-inf'), 0)
		left = self.isBst(root.left)
		right = self.isBst(root.right)
		if left.maxi < root.data < right.mini:
			return help(min(root.data, left.mini), max(root.data, right.maxi), 1 + left.size + right.size)
		else:
			return help(float('-inf'), float('inf'), max(right.size, left.size))

	def largestBst(self, root):
		res = self.isBst(root)
		return res.size


class Solution:

	def largestBst(self, root):
		if root == None:
			return 0
		if self.isbst(root, -9999, 99999):
			return self.size(root)
		return max(self.largestBst(root.left), self.largestBst(root.right))

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

	def size(self, root):
		if root == None:
			return 0
		return self.size(root.left) + self.size(root.right) + 1


class MyNode:

	def __init__(self, size, mn, mx):
		self.size = size
		self.min = mn
		self.max = mx

class Solution:

	def dfs(self, node):
		if not node:
			return MyNode(0, sys.maxsize, -sys.maxsize)
		left = self.dfs(node.left)
		right = self.dfs(node.right)
		if left.max < node.data and node.data < right.min:
			return MyNode(left.size + right.size + 1, min(left.min, node.data), max(right.max, node.data))
		return MyNode(max(left.size, right.size), -sys.maxsize, sys.maxsize)

	def largestBst(self, root):
		res = self.dfs(root)
		return res.size


class Solution:

	def largestBst(self, root):
		if root is None:
			return 0
		if self.check(root, -100000, 100000):
			return self.size(root)
		return max(self.largestBst(root.left), self.largestBst(root.right))

	def size(self, root):
		if root is None:
			return 0
		return 1 + (self.size(root.left) + self.size(root.right))

	def check(self, root, mini, maxi):
		if root is None:
			return True
		if root.data <= mini or root.data >= maxi:
			return False
		return self.check(root.left, mini, root.data) and self.check(root.right, root.data, maxi)


class Solution:

	def largestBst(self, root):
		self.res = 0

		def helper(root):
			if not root:
				return [float('inf'), float('-inf'), 0]
			left = helper(root.left)
			right = helper(root.right)
			if root.data > left[1] and root.data < right[0]:
				height = 1 + left[2] + right[2]
				self.res = max(self.res, height)
				return [min(root.data, left[0]), max(root.data, right[1]), height]
			return [float('-inf'), float('inf'), 0]
		helper(root)
		return self.res


class NodeValue:

	def __init__(self, maximum, minimum, size):
		self.maxNode = maximum
		self.minNode = minimum
		self.size = size

class Solution:

	def solve(self, root):
		if not root:
			return NodeValue(float('-inf'), float('inf'), 0)
		if root.left == None and root.right == None:
			return NodeValue(root.data, root.data, 1)
		l = self.solve(root.left)
		r = self.solve(root.right)
		if l.maxNode < root.data < r.minNode:
			return NodeValue(max(r.maxNode, root.data), min(l.minNode, root.data), 1 + l.size + r.size)
		return NodeValue(float('inf'), float('-inf'), max(l.size, r.size))

	def largestBst(self, root):
		ans = self.solve(root)
		return ans.size


class Solution:

	def largestBst(self, root):
		size = [0]
		self.dfs_bst(root, size)
		return size[0]

	def dfs_bst(self, root, size):
		if root == None:
			return (True, 0, float('inf'), float('-inf'))
		(left_is_bst, left_size, left_min, left_max) = self.dfs_bst(root.left, size)
		(right_is_bst, right_size, right_min, right_max) = self.dfs_bst(root.right, size)
		if left_is_bst and right_is_bst and (left_max < root.data < right_min):
			size[0] = max(size[0], left_size + right_size + 1)
			return (True, left_size + right_size + 1, min(left_min, root.data), max(right_max, root.data))
		else:
			return (False, 0, 0, 0)


class Solution:
	global c

	def b(self, r):
		global c
		if not r:
			return [0, float('+inf'), float('-inf'), True]
		if not r.left and (not r.right):
			return [1, r.data, r.data, True]
		l = self.b(r.left)
		ri = self.b(r.right)
		if l[3] and ri[3] and (l[2] < r.data) and (r.data < ri[1]):
			c = max(c, l[0] + ri[0] + 1)
			return [l[0] + ri[0] + 1, min(l[1], r.data), max(ri[2], r.data), True]
		return [max(l[0], ri[0]), float('-inf'), float('+inf'), False]

	def largestBst(self, root):
		global c
		c = 0
		self.b(root)
		if c == 0:
			return 1
		return c


class Solution:

	def largestBst(self, root):
		if root == None:
			return 0
		if self.isbst(root, -1000000, 100000000):
			return self.size(root)
		return max(self.largestBst(root.left), self.largestBst(root.right))

	def size(self, root):
		if root == None:
			return 0
		return 1 + self.size(root.left) + self.size(root.right)

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


class Node1:

	def __init__(self, isBst, size, mini, maxi):
		self.isBst = isBst
		self.size = size
		self.mini = mini
		self.maxi = maxi

def bst(root):
	if not root:
		x = Node1(True, 0, 1000000, 0)
		return x
	left = bst(root.left)
	right = bst(root.right)
	if left.isBst and right.isBst and (root.data > left.maxi) and (root.data < right.mini):
		x = Node1(True, 1 + left.size + right.size, min(root.data, left.mini), max(root.data, right.maxi))
	else:
		x = Node1(False, max(left.size, right.size), 1000000, 0)
	return x

class Solution:

	def largestBst(self, root):
		return bst(root).size


class BstNode:

	def __init__(self, size=0, smallest=float('inf'), largest=float('-inf')):
		self.smallest = smallest
		self.largest = largest
		self.size = size

class Solution:

	def solve(self, root):
		if root is None:
			return BstNode()
		leftBst = self.solve(root.left)
		rightBst = self.solve(root.right)
		if leftBst.largest < root.data and rightBst.smallest > root.data:
			if root.left is not None:
				currSmallest = leftBst.smallest
			else:
				currSmallest = root.data
			if root.right is not None:
				currLargest = rightBst.largest
			else:
				currLargest = root.data
			currSize = leftBst.size + rightBst.size + 1
		else:
			currSmallest = float('-inf')
			currLargest = float('inf')
			currSize = max(leftBst.size, rightBst.size)
		return BstNode(currSize, currSmallest, currLargest)

	def largestBst(self, root):
		bstNode = self.solve(root)
		return bstNode.size


class Solution:

	def solve(self, root, Min, Max, res):
		if root.left is None and root.right is None:
			Min[0] = root.data
			Max[0] = root.data
			res[0] = max(res[0], 1)
			return 1
		ans1 = 0
		min1 = float('inf')
		max1 = float('-inf')
		if root.left is not None:
			count = self.solve(root.left, Min, Max, res)
			if count != -1 and Max[0] < root.data:
				ans1 = count
			else:
				ans1 = -1
			min1 = Min[0]
			max1 = Max[0]
		ans2 = 0
		if root.right is not None:
			count = self.solve(root.right, Min, Max, res)
			if count != -1 and Min[0] > root.data:
				ans2 = count
			else:
				ans2 = -1
		Min[0] = min(Min[0], min1, root.data)
		Max[0] = max(Max[0], max1, root.data)
		if ans1 != -1 and ans2 != -1:
			res[0] = max(res[0], ans1 + ans2 + 1)
			return ans1 + ans2 + 1
		return -1

	def largestBst(self, root):
		res = [0]
		self.solve(root, [float('inf')], [float('-inf')], res)
		return res[0]


class TreeNode:

	def __init__(self, maxi, mini, isbst, size):
		self.maxi = maxi
		self.mini = mini
		self.isbst = isbst
		self.size = size

class Solution:

	def largestBst(self, root):

		def solve(root):
			if not root:
				return TreeNode(~sys.maxsize, sys.maxsize, True, 0)
			left = solve(root.left)
			right = solve(root.right)
			if left.isbst and right.isbst and (root.data > left.maxi) and (root.data < right.mini):
				curr_maxi = max(root.data, right.maxi)
				curr_mini = min(left.mini, root.data)
				curr_isbst = True
				curr_size = left.size + right.size + 1
				return TreeNode(curr_maxi, curr_mini, curr_isbst, curr_size)
			return TreeNode(~sys.maxsize, sys.maxsize, False, max(left.size, right.size))
		return solve(root).size


class isBst:

	def __init__(self, is_bst, total_node=1, min=float('-inf'), max=float('inf')):
		self.bst = is_bst
		self.length = total_node
		self.min = min
		self.max = max

	def __str__(self):
		return str(self.bst) + ', ' + str(self.length) + ', ' + str(self.min) + ', ' + str(self.max)

class Solution:

	def largestBst(self, root):
		no_of_node = [0]

		def rec(node):
			if node.left is None and node.right is None:
				return isBst(True, 1, node.data, node.data)
			left = rec(node.left) if node.left else isBst(True, 0, node.data, node.data - 1)
			right = rec(node.right) if node.right else isBst(True, 0, node.data + 1, node.data)
			if left.bst and right.bst:
				if left.max < node.data < right.min:
					return isBst(True, left.length + right.length + 1, left.min, right.max)
			return isBst(False, max(left.length, right.length))
		return rec(root).length

	def check_bst(self, root, no_of_node, low=float('-inf'), high=float('inf')):
		if root is None:
			return True
		no_of_node[0] += 1
		if not low < root.data < high:
			return False
		return self.check_bst(root.left, no_of_node, low, root.data) and self.check_bst(root.right, no_of_node, root.data, high)


class Solution:

	def largestBst(self, root):
		no_of_node = [0]

		def traverse(node):
			if node is None:
				return 0
			node_count = [0]
			if self.check_bst(node, node_count):
				return node_count[0]
			return max(traverse(node.right), traverse(node.left))
		return traverse(root)

	def check_bst(self, root, no_of_node, low=float('-inf'), high=float('inf')):
		if root is None:
			return True
		no_of_node[0] += 1
		if not low < root.data < high:
			return False
		return self.check_bst(root.left, no_of_node, low, root.data) and self.check_bst(root.right, no_of_node, root.data, high)


class NodeValue:

	def __init__(self, minNode, maxNode, maxSize):
		self.minNode = minNode
		self.maxNode = maxNode
		self.maxSize = maxSize

class Solution:

	def largestBst(self, root):
		return self.largestBstHelper(root).maxSize

	def largestBstHelper(self, root):
		if root is None:
			return NodeValue(float('inf'), float('-inf'), 0)
		left = self.largestBstHelper(root.left)
		right = self.largestBstHelper(root.right)
		if left.maxNode < root.data and root.data < right.minNode:
			return NodeValue(min(root.data, left.minNode), max(root.data, right.maxNode), 1 + left.maxSize + right.maxSize)
		return NodeValue(float('-inf'), float('inf'), max(left.maxSize, right.maxSize))


class Solution:

	def tt(self, root):
		if root == None:
			return (True, 1000001, -1, 0)
		if root.left == None and root.right == None:
			return (True, root.data, root.data, 1)
		(islbst, lmin, lmax, nl) = self.tt(root.left)
		(isrbst, rmin, rmax, nr) = self.tt(root.right)
		mini = min(lmin, rmin, root.data)
		maxi = max(lmax, rmax, root.data)
		if islbst == False or isrbst == False:
			return (False, mini, maxi, max(nr, nl))
		if root.data <= lmax or root.data >= rmin:
			nmaxi = max(nr, nl)
			return (False, mini, maxi, nmaxi)
		return (True, mini, maxi, nl + nr + 1)

	def largestBst(self, root):
		(isbst, mini, maxi, n) = self.tt(root)
		return n


class Solution:

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

	def __init__(self):
		self.res = 0

	def su(self, root):
		if root == None:
			return 0
		return 1 + self.su(root.left) + self.su(root.right)

	def largestBst(self, root):
		if not root:
			return 0
		if self.Valid(root, None, None):
			ans = self.su(root)
			self.res = max(ans, self.res)
		self.largestBst(root.left)
		self.largestBst(root.right)
		return self.res


class Solution:

	def largestBst(self, root):
		ans = [0]

		def solve(root):
			if root == None:
				return [999999, -999999, 0, True]
			left = solve(root.left)
			right = solve(root.right)
			left_min = min(root.data, left[0], right[0])
			right_max = max(root.data, left[1], right[1])
			size = left[2] + right[2] + 1
			if root.data <= left[1] or root.data >= right[0]:
				return [left_min, right_max, size, False]
			if left[3] and right[3]:
				ans[0] = max(size, ans[0])
				return [left_min, right_max, size, True]
			return [left_min, right_max, size, False]
		solve(root)
		return ans[0]


class NodeValue:

	def __init__(self, mini, maxi, maxsize):
		self.mini = mini
		self.maxi = maxi
		self.maxsize = maxsize

class Solution:

	def helper(self, root):
		if not root:
			return NodeValue(float('inf'), float('-inf'), 0)
		left = self.helper(root.left)
		right = self.helper(root.right)
		if left.maxi < root.data < right.mini:
			return NodeValue(min(root.data, left.mini), max(right.maxi, root.data), 1 + left.maxsize + right.maxsize)
		return NodeValue(float('-inf'), float('inf'), max(left.maxsize, right.maxsize))

	def largestBst(self, root):
		return self.helper(root).maxsize


class Solution:

	def largestBst(self, root):

		def large(root):
			if root is None:
				return [float('inf'), float('-inf'), 0]
			if root.left is None and root.right is None:
				return [root.data, root.data, 1]
			left = large(root.left)
			right = large(root.right)
			ans = [0, 0, 0]
			if root.data > left[1] and root.data < right[0]:
				ans[0] = min(left[0], right[0], root.data)
				ans[1] = max(left[1], right[1], root.data)
				ans[2] = left[2] + right[2] + 1
				return ans
			ans = [float('-inf'), float('inf'), max(left[2], right[2])]
			return ans
		return large(root)[2]


class Solution:

	def largestBst(self, root):

		def recurDown(root: Node):
			if not root:
				return [0, 1000000000, -1000000000]
			if (not root.left) & (not root.right):
				return [1, root.data, root.data]
			rightData = recurDown(root.right)
			leftData = recurDown(root.left)
			if rightData[1] > root.data and leftData[2] < root.data:
				if rightData[0] <= 0:
					return [rightData[0] + leftData[0] + 1, leftData[1], root.data]
				if leftData[0] <= 0:
					return [rightData[0] + leftData[0] + 1, root.data, rightData[2]]
				return [rightData[0] + leftData[0] + 1, leftData[1], rightData[2]]
			else:
				return [max(rightData[0], leftData[0]), -1000000000, 1000000000]
		return recurDown(root)[0]


class Solution:

	def largestBst(self, root):
		bestsizes = [0, 0]

		def recurDown(root: Node):
			nonlocal bestsizes
			if not root:
				return [0, 0, 0]
			if (not root.left) & (not root.right):
				return [1, root.data, root.data]
			if not root.left:
				rightData = recurDown(root.right)
				if rightData[0] == -1:
					return rightData
				if rightData[1] > root.data:
					rightData[0] = rightData[0] + 1
					rightData[1] = root.data
					return rightData
				else:
					bestsizes.append(rightData[0])
					return [-1, 0, 0]
			if not root.right:
				leftData = recurDown(root.left)
				if leftData[0] == -1:
					return leftData
				if leftData[2] < root.data:
					leftData[0] = leftData[0] + 1
					leftData[2] = root.data
					return leftData
				else:
					bestsizes.append(leftData[0])
					return [-1, 0, 0]
			rightData = recurDown(root.right)
			leftData = recurDown(root.left)
			if rightData[0] != -1 and leftData[0] != -1:
				if rightData[1] > root.data and leftData[2] < root.data:
					return [rightData[0] + leftData[0] + 1, leftData[1], rightData[2]]
				else:
					bestsizes.append(rightData[0])
					bestsizes.append(leftData[0])
					return [-1, 0, 0]
			else:
				bestsizes.append(rightData[0])
				bestsizes.append(leftData[0])
				return [-1, 0, 0]
		return max(recurDown(root)[0], max(bestsizes))


class Solution:

	def largestBst(self, root):

		def f_s(root):
			if root:
				(ls, ll, s1) = f_s(root.left)
				(rl, rs, s2) = f_s(root.right)
				if root.data > ll and root.data < rl:
					return (min(root.data, ls), max(root.data, rs), s1 + s2 + 1)
				else:
					return (0, 10000000, max(s1, s2))
			return (10000000, 0, 0)
		(s3, s4, s5) = f_s(root)
		return s5


class Solution:

	def largestBst(self, root):

		def rec(root):
			if root is None:
				return [True, 2 ** 31, -2 * 31, 0]
			if root.left is None and root.right is None:
				return [True, root.data, root.data, 1]
			l = rec(root.left)
			r = rec(root.right)
			if l[0] and r[0] and (l[2] < root.data) and (r[1] > root.data):
				return [True, min(l[1], root.data), max(root.data, r[2]), l[3] + r[3] + 1]
			else:
				return [False, min(l[1], root.data), max(root.data, r[2]), max(l[3], r[3])]
		return rec(root)[3]


import math

class Solution:

	def largestBst(self, root):

		def preorder(node):
			if not node or node == None:
				return [math.inf, -math.inf, 0]
			left = preorder(node.left)
			right = preorder(node.right)
			if node.data > left[1] and node.data < right[0]:
				return [min(node.data, left[0]), max(node.data, right[1]), left[2] + right[2] + 1]
			else:
				return [-math.inf, math.inf, max(left[2], right[2])]
		return preorder(root)[2]


class Solution:

	def largestBst(self, root):
		if not root:
			return 0
		self.largest_val = 1
		self.dfs(root)
		return self.largest_val

	def dfs(self, root):
		if not root:
			return (False, 0, -10001, 10001)
		if not root.left and (not root.right):
			return (True, 1, root.data, root.data)
		(l_is_bst, l_size, l_min, l_max) = self.dfs(root.left)
		(r_is_bst, r_size, r_min, r_max) = self.dfs(root.right)
		if l_is_bst and r_is_bst and (l_max < root.data < r_min):
			curr_size = 1 + l_size + r_size
			self.largest_val = max(self.largest_val, curr_size)
			return (True, curr_size, l_min, r_max)
		elif l_is_bst and l_max < root.data and (not root.right):
			curr_size = 1 + l_size
			self.largest_val = max(self.largest_val, curr_size)
			return (True, curr_size, l_min, root.data)
		elif r_is_bst and root.data < r_min and (not root.left):
			curr_size = 1 + r_size
			self.largest_val = max(self.largest_val, curr_size)
			return (True, curr_size, root.data, r_max)
		else:
			return (False, 0, -10001, 10001)


class Solution:

	def largestBst(self, root):
		self.res = 1

		def dfs(root):
			if not root:
				return (True, 2 ** 31, -2 * 31, 0)
			if not root.left and (not root.right):
				return (True, root.data, root.data, 1)
			(lbst, lmin, lmax, lcount) = dfs(root.left)
			(rbst, rmin, rmax, rcount) = dfs(root.right)
			if lbst and rbst and (lmax < root.data < rmin):
				self.res = max(self.res, 1 + lcount + rcount)
				return (True, min(lmin, root.data), max(rmax, root.data), 1 + lcount + rcount)
			else:
				return (False, root.data, root.data, 0)
		dfs(root)
		return self.res


class Solution:

	def largestBst(self, root):
		self.res = 1

		def dfs(root):
			if not root:
				return (True, 2 ** 31, -2 * 31, 0)
			left = dfs(root.left)
			right = dfs(root.right)
			if left[2] < root.data < right[1] and left[0] and right[0]:
				self.res = max(self.res, 1 + left[3] + right[3])
				return (True, min(left[1], root.data), max(right[2], root.data), 1 + left[3] + right[3])
			else:
				return (False, min(left[1], root.data), max(right[2], root.data), 1 + left[3] + right[3])
		dfs(root)
		return self.res