# Straightforward Python O(n) solution

• In a BST, a root node is greater than any node in left sub-tree and less than any node in right sub-tree. Thus, when backtracking, we need three variables to store the information of empty or illegal BST and MAX, MIN value of this sub-tree.

``````class Solution(object):
def largestBSTSubtree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root):
if not root:
return (-1, -1, -1) # status, min, max
if not root.left and not root.right:
return (1, root.val, root.val)

median = root.val
left = dfs(root.left)
right = dfs(root.right)
if left[0] > 0 and right[0] > 0 and median > left[2] and median < right[1]:
self.maxBST = max(self.maxBST, left[0] + right[0] + 1)
return (left[0] + right[0] + 1, left[1], right[2])

if left[0] == -1 and right[0] > 0 and median < right[1]:
self.maxBST = max(self.maxBST, right[0] + 1)
return (right[0] + 1, median, right[2])

if left[0] > 0 and right[0] == -1 and median > left[2]:
self.maxBST = max(self.maxBST, left[0] + 1)
return (left[0] + 1, left[1], median)
return (0, -1, -1)

if not root:
return 0
self.maxBST = 1
dfs(root)
return self.maxBST
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.