333. Largest BST Subtree

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. Here's an example:

    10
    / \
   5  15
  / \   \ 
 1   8   7

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

Related Issue 98 Validate Binary Search Tree

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    /*
        1. you need to track each subtree is bst or not.
        2. you need to track the size of subtree if it is a bst.
        3. thus global variable/TreeNode won't keep consistent info
            regarding 1&2.
        4. you need a wrapper to hold such 2 information. along with the
            current range of substree.

    */
    class Node{
        int size;
        int left,right;
        boolean isBst;
        Node(){
            size = 0;
            isBst = true;
            left = Integer.MAX_VALUE;
            right = Integer.MIN_VALUE;
        }
    }
    public int largestBSTSubtree(TreeNode root) {

        Node n = isBST(root);
        return n.size;
    }

    Node isBST(TreeNode root){
        Node node = new Node();
        if(root == null){
            return node;
        }

        Node l = isBST(root.left);
        Node r = isBST(root.right);

        node.left = Math.min(l.left, root.val);
        node.right = Math.max(r.right, root.val);

        if(l.isBst && r.isBst && l.right <= root.val && r.left >= root.val){
            node.size = l.size + r.size +1;
            node.isBst = true;
        }else{
            node.size = Math.max(l.size, r.size);
            node.isBst = false;
        }

        return node;
    }
}