## Description

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Input: [10,5,15,1,8,null,7]

10
/ \
5  15
/ \   \
1   8   7

Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
The return value is the subtree's size, which is 3.



Note:

• A subtree must include all of its descendants.

## Solutions

### 1. Recursion

# Time:  O(n)
# Space: O(h)

class Solution(object):
def largestBSTSubtree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root is None:
return 0

max_size = 
def largestBSTSubtreeHelper(root):
if root.left is None and root.right is None:
return 1, root.val, root.val

left_size, left_min, left_max = 0, root.val, root.val
if root.left is not None:
left_size, left_min, left_max = largestBSTSubtreeHelper(root.left)

right_size, right_min, right_max = 0, root.val, root.val
if root.right is not None:
right_size, right_min, right_max = largestBSTSubtreeHelper(root.right)

size = 0
if (root.left is None or left_size > 0) and \
(root.right is None or right_size > 0) and \
left_max <= root.val <= right_min:
size = 1 + left_size + right_size
max_size = max(max_size, size)

return size, left_min, right_max

largestBSTSubtreeHelper(root)
return max_size