Largest BST in a Binary Tree

#1

please tell the approach to solve this question

#2

hey @Anubhav44044
The basic idea used here is that for a tree with root as currentNode to be a valid BST, it’s left and right sub-trees have to be valid BSTs, value of currentNode has to be greater than the maximum valued node from its left sub-tree and value of currentNode has to be less than the minimum valued node from its right sub-tree.

To check for above conditions, we return value of maximum valued node, minimum valued node and boolean variable stating if the tree is valid BST or not from every sub-tree. We also return size of a sub-tree if it is a valid BST or return -1 if it is not a valid BST. Using these returned variables from left and right sub-trees, we can check at the currentNode if the tree with its root as currentNode is a validBST or not. If the tree is a valid BST, we calculate size of tree using (1+sizeOfLeftSubtree +sizeOfRightSubtree) and return that along with other variables stated above. If it is not a valid BST we return -1 along with other variables.

  class Info {
        int size;
        int max;
        int min;
        int ans;
        boolean isBST;

        Info() {

        }

        Info(int s, int max, int min, int ans, boolean isBST) {
            this.size = s;
            this.max = max;
            this.min = min;
            this.ans = ans;
            this.isBST = isBST;
        }
    }

    public int largestBSTinBT() {
        return this.largestBSTinBT(this.root).ans;
    }

    private Info largestBSTinBT(Node root) {
        if (root == null) {
            return new Info(0, Integer.MIN_VALUE, Integer.MAX_VALUE, 0, true);
        }
        if (root.left == null && root.right == null) {
            return new Info(1, root.data, root.data, 1, true);
        }

        Info l = largestBSTinBT(root.left);
        Info r = largestBSTinBT(root.right);

        Info ret = new Info();
        ret.size = (1 + l.size + r.size);

        if (l.isBST && r.isBST && l.max < root.data && r.min > root.data) {
            ret.min = Math.min(l.min, Math.min(r.min, root.data));
            ret.max = Math.max(r.max, Math.max(l.max, root.data));
            ret.ans = ret.size;
            ret.isBST = true;
            return ret;
        }

        ret.ans = Math.max(l.ans, r.ans);
        ret.isBST = false;
        return ret;
    }
#3

is there any other method to do it in same complexity??

#4

is there any other method to do it in same complexity??
Answer Nope.
But you can do it O(N^2)