# Short Python solution

• ``````def largestBSTSubtree(self, root):
def dfs(root):
if not root:
return 0, 0, float('inf'), float('-inf')
N1, n1, min1, max1 = dfs(root.left)
N2, n2, min2, max2 = dfs(root.right)
n = n1 + 1 + n2 if max1 < root.val < min2 else float('-inf')
return max(N1, N2, n), n, min(min1, root.val), max(max2, root.val)
return dfs(root)[0]
``````

My `dfs` returns four values:

• `N` is the size of the largest BST in the tree.
• If the tree is a BST, then `n` is the number of nodes, otherwise it's -infinity.
• If the tree is a BST, then `min` and `max` are the minimum/maximum value in the tree.

• smart to set n to -infinity when it's not BST! all the parents node will have size -infinity too, so no need to add another attribute for isBST

• Wow, this `-inf` trick saves a lot of comparison.

• Mine is very similar to yours:

``````class Solution(object):
def largestBSTSubtree(self, root):
def solve(root, maxval):
if not root: return 0, float('inf'), -float('inf')
left,  minvl, maxvl = solve(root.left, maxval)
right, minvr, maxvr = solve(root.right, maxval)
if left == -1 or right == -1 or not maxvl < root.val < minvr:
return -1, 0, 0
maxval[0] = max(maxval[0], 1 + left + right)
return 1 + left + right, min(root.val, minvl, minvr), max(root.val, maxvr, maxvl)

maxval = [0]
solve(root, maxval)
return maxval[0]

# 71 / 71 test cases passed.
# Status: Accepted
# Runtime: 100 ms

``````

• smart solution !

• Below gave faster run time , probably because it terminates as soon as it finds a largest BST - even though asymptotic complexity is not O(n). Worst case performance is likely only when its there're no BST greater than size 1 (leaf)

``````class Solution(object):
def largestBSTSubtree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def isbst(root, minv, maxv):
if root:
return minv < root.val < maxv and isbst(root.left, minv, root.val) and isbst(root.right, root.val, maxv)
return True

def size(root):
if root:
return size(root.left) + size(root.right) + 1
return 0

if not root:
return 0

sentinel = TreeNode(None)
q    = []
ans  = 0
q.append(root)
q.append(sentinel)
while q:
node = q.pop(0)
if node is sentinel:
if ans > 1:
return ans
if q:
q.append(sentinel)
continue

if isbst(node, -float('inf'), float('inf')):
#print('isbst', node.val)
ans = max(ans,size(node))
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return ans
``````

Also inspired by this code, I wrote following, which led to double the run time - looks like namedtuple incur overhead

``````class Solution(object):
def largestBSTSubtree(self, root):
"""
:type root: TreeNode
:rtype: int
"""

self.ans = 0
Result = collections.namedtuple('Result', ['isBst', 'size', 'minv', 'maxv'])

def func(root, minv, maxv):
if root:
left = func(root.left, minv, root.val)
right = func(root.right, root.val, maxv)
isBst = left.isBst and right.isBst and left.maxv < root.val < right.minv
size = 0
if left.isBst:
self.ans = max(self.ans, left.size)
if right.isBst:
self.ans = max(self.ans, right.size)
if isBst:
size = left.size + 1 + right.size
self.ans = max(self.ans, size)
minv = min(left.minv, root.val)
maxv = max(right.maxv, root.val)
return Result(isBst, size, minv, maxv)

return Result(isBst=True, size=0, minv=float('inf'), maxv=-float('inf'))

func(root, -float('inf'), float('inf'))
return self.ans
``````

• @sha256pki said in Short Python solution:

Below gave faster run time

Such statements are useless. Because almost always, people don't measure properly. So such statements can't be trusted. How much faster, and how consistently? How often did you submit each? What were the individual times? What were the average times?

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