333. Largest BST Subtree (M)

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.

Follow up:

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

Solution:

Related Issue 98 Validate Binary Search Tree

Version 1: Brute force:

 class GFG {
 
    int largestBST(Node root)
    {
        if (root == null)
            return 0;
 
        if (isBST(root))
            return size(root);
 
        return Math.max(largestBST(root.left),
                        largestBST(root.right));
    }
}

Version 2:

这题的确跟98很像，但是这题要从leaf往上做才能达到O（n）

in version , we traverse the tree in top-down manner and do BST test for every node. If we traverse the tree in bottom-up manner, then we can pass information about subtrees to the parent. The passed information can be used by the parent to do BST test (for parent node) only in constant time (or O(1) time). A left subtree need to tell the parent whether it is BST or not and also needs to pass maximum value in it. So that we can compare the maximum value with the parent’s data to check the BST property. Similarly, the right subtree need to pass the minimum value up the tree. The subtrees need to pass the following information up the tree for the finding the largest BST.

1. Whether the subtree itself is BST or not

2. If the subtree is left subtree of its parent, then maximum value in it. And if it is right subtree then minimum value in it.

3. Size of this subtree if this subtree is BST (In the following code, return value of largestBSTtil() is used for this purpose) max_ref is used for passing the maximum value up the tree and min_ptr is used for passing minimum value up the tree.

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

        helper(root);

        return max;
    }

    private ResultType helper(TreeNode root) {
        if (root == null) {
            // return size = 0, -infinity, +infinity - so that we can return the leaf value up
            return new ResultType(0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        ResultType left = helper(root.left);
        ResultType right = helper(root.right);

        // -1 means invalid BST, so we stop adding the nodes up if either subtree is not BST
        // if root's value is smaller than high of left || bigger than low of right
        // means it's not a BST, return -1 up
        if (left.size == -1 || right.size == -1 || root.val <= left.hight || root.val >= right.low) {
            return new ResultType(-1, 0, 0);// doesn't matter what the bound is for non BST
        }

        // if we are here means, both left & right & current node is valid BST, add them up
        int curSize = left.size + right.size + 1;
        max = Math.max(max, curSize); // update global max

        // return the size, and min
        return new ResultType(curSize, Math.min(left.low, root.val), Math.max(right.hight, root.val));
    }
}

class ResultType {
    int size; // size of this subtree
    int low; // the lower bound that's valid
    int hight; // the upper bound that's valid

    public ResultType(int s, int l, int h) {
        size = s;
        low = l;
        hight = h;
    }
}

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;
    }
}

*******

public class Solution {
    private class State {
        public boolean isBST;
        public int min;
        public int max;
        public int num;
        public State(boolean isBST, int min, int max, int num) {
            this.isBST = isBST;
            this.min = min;
            this.max = max;
            this.num = num;
        }
    }
    private int max = 0;
    public int largestBSTSubtree(TreeNode root) {
        max = 0;
        lbst(root);
        return max;
    }
    private State lbst(TreeNode node) {
        State result = null;
        if (node == null) {
            return result;
        }
        State left = lbst(node.left);
        State right = lbst(node.right);
        if ((left == null || (left.isBST && node.val > left.max)) && (right == null || (right.isBST && node.val < right.min))) {
            //A valid BST
            int newMin = left == null?node.val:left.min;
            int newMax = right == null?node.val:right.max;
            int newNum = (left == null?0:left.num) + (right == null?0:right.num) + 1;
            max = Math.max(max, newNum);
            return new State(true, newMin, newMax, newNum);
        }
        return new State(false, 0, 0, 0);
    }
}