# Question

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.

Note: A subtree must include all of its descendants.

Example:

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.


Can you figure out ways to solve it with O(n) time complexity?

# Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
int maxSize = 1;

public int largestBSTSubtree(TreeNode root) {
if(root == null) return 0;
isBST(root);
return maxSize;
}

// [BST size, min, max]
private int[] isBST(TreeNode root) {
if(root.left == null && root.right == null)
return new int[]{1, root.val, root.val};

int[] left = null, right = null;

if(root.left != null)
left = isBST(root.left);
if(root.right != null)
right = isBST(root.right);
int size = 1, min = root.val, max = root.val;
if(left != null) {
if(left[0] != -1 && root.val > left[2]) {
size += left[0];
min = left[1];
} else return new int[]{-1, 0, 0};
}
if(right != null) {
if(right[0] != -1 && root.val < right[1]) {
size += right[0];
max = right[2];
} else return new int[]{-1, 0, 0};
}
maxSize = Math.max(maxSize, size);
return new int[]{size, min, max};
}
}