Find the largest BST subtree in a given Binary Tree

Related: LeetCode 333 - Largest BST Subtree
Find the largest BST subtree in a given Binary Tree | GeeksforGeeks
Given a Binary Tree, write a function that returns the size of the largest subtree which is also a Binary Search Tree (BST). If the complete Binary Tree is BST, then return the size of whole tree.

Input: 
       50
     /    \
  30       60
 /  \     /  \ 
5   20   45    70
              /  \
            65    80
Output: 5
The following subtree is the maximum size BST subtree 
      60
     /  \ 
   45    70
        /  \
      65    80

https://www.geeksforgeeks.org/largest-bst-binary-tree-set-2/

The idea is based on method 3 of check if a binary tree is BST article.

A Tree is BST if following is true for every node x.

1. The largest value in left subtree (of x) is smaller than value of x.
2. The smallest value in right subtree (of x) is greater than value of x.

We traverse tree in bottom up manner. For every traversed node, we return maximum and minimum values in subtree rooted with it. If any node follows above properties and size of

struct Info

{

    int sz; // Size of subtree

    int max; // Min value in subtree

    int min; // Max value in subtree

    int ans; // Size of largest BST which

    // is subtree of current node

    bool isBST; // If subtree is BST

};

  

// Returns Information about subtree. The

// Information also includes size of largest

// subtree which is a BST.

Info largestBSTBT(Node* root)

{

    // Base cases : When tree is empty or it has

    // one child.

    if (root == NULL)

        return {0, INT_MIN, INT_MAX, 0, true};

    if (root->left == NULL && root->right == NULL)

        return {1, root->data, root->data, 1, true};

  

    // Recur for left subtree and right subtrees

    Info l = largestBSTBT(root->left);

    Info r = largestBSTBT(root->right);

  

    // Create a return variable and initialize its

    // size.

    Info ret;

    ret.sz = (1 + l.sz + r.sz);

  

    // If whole tree rooted under current root is

    // BST.

    if (l.isBST && r.isBST && l.max < root->data &&

            r.min > root->data)

    {

        ret.min = min(l.min, min(r.min, root->data));

        ret.max = max(r.max, max(l.max, root->data));

  

        // Update answer for tree rooted under

        // current 'root'

        ret.ans = ret.sz;

        ret.isBST = true;

  

        return ret;

    }

  

    // If whole tree is not BST, return maximum

    // of left and right subtrees

    ret.ans = max(l.ans, r.ans);

    ret.isBST = false;

  

    return ret;

}




Method 2 (Tricky and Efficient)
Key Point: PostOrderTraveral

In method 1, 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 need 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 (In the following code, is_bst_ref is used for this purpose)
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 largestBST(Node node) {

  

        largestBSTUtil(node, val, val, val, val);

  

        return val.max_size;

    }

  

    /* largestBSTUtil() updates *max_size_ref for the size of the largest BST

     subtree.   Also, if the tree rooted with node is non-empty and a BST,

     then returns size of the tree. Otherwise returns 0.*/

    int largestBSTUtil(Node node, Value min_ref, Value max_ref,

            Value max_size_ref, Value is_bst_ref) {

  

        /* Base Case */

        if (node == null) {

            is_bst_ref.is_bst = true; // An empty tree is BST

            return 0;    // Size of the BST is 0

        }

  

        int min = Integer.MAX_VALUE;

  

        /* A flag variable for left subtree property

         i.e., max(root->left) < root->data */

        boolean left_flag = false;

  

        /* A flag variable for right subtree property

         i.e., min(root->right) > root->data */

        boolean right_flag = false;

  

        int ls, rs; // To store sizes of left and right subtrees

  

        /* Following tasks are done by recursive call for left subtree

         a) Get the maximum value in left subtree (Stored in *max_ref)

         b) Check whether Left Subtree is BST or not (Stored in *is_bst_ref)

         c) Get the size of maximum size BST in left subtree (updates *max_size) */

        max_ref.max = Integer.MIN_VALUE;

        ls = largestBSTUtil(node.left, min_ref, max_ref, max_size_ref, is_bst_ref);

        if (is_bst_ref.is_bst == true && node.data > max_ref.max) {

            left_flag = true;

        }

  

        /* Before updating *min_ref, store the min value in left subtree. So that we

         have the correct minimum value for this subtree */

        min = min_ref.min;

  

        /* The following recursive call does similar (similar to left subtree) 

         task for right subtree */

        min_ref.min = Integer.MAX_VALUE;

        rs = largestBSTUtil(node.right, min_ref, max_ref, max_size_ref, is_bst_ref);

        if (is_bst_ref.is_bst == true && node.data < min_ref.min) {

            right_flag = true;

        }

  

        // Update min and max values for the parent recursive calls

        if (min < min_ref.min) {

            min_ref.min = min;

        }

        if (node.data < min_ref.min) // For leaf nodes

        {

            min_ref.min = node.data;

        }

        if (node.data > max_ref.max) {

            max_ref.max = node.data;

        }

  

        /* If both left and right subtrees are BST. And left and right

         subtree properties hold for this node, then this tree is BST.

         So return the size of this tree */

        if (left_flag && right_flag) {

            if (ls + rs + 1 > max_size_ref.max_size) {

                max_size_ref.max_size = ls + rs + 1;

            }

            return ls + rs + 1;

        } else {

            //Since this subtree is not BST, set is_bst flag for parent calls

            is_bst_ref.is_bst = false;

            return 0;

        }

    }




Method 1 (Simple but inefficient) O(n*n)

int largestBST(struct node *root)

{

   if (isBST(root))

     return size(root);

   else

    return max(largestBST(root->left), largestBST(root->right));

}

http://leetcode.com/2010/11/largest-binary-search-tree-bst-in.html
http://www.crazyforcode.com/find-largest-bst-binary-tree/

struct node* findLargestBSTSubtree(struct node *root) {

struct node *bstRoot = NULL;

int min, max;

int maxNodes = INT_MIN;

largestBST(root, min, max, maxNodes,bstRoot);

return bstRoot;

}

int largestBST(struct node* root, int& min, int& max, int& size,struct node* & bstRoot)

{

if(root == NULL)

return 0;

int leftMin = INT_MIN, rightMin = INT_MIN;

int leftMax = INT_MAX, rightMax = INT_MAX;

int x,y;

x = largestBST(root->left, leftMin, leftMax, size,bstRoot);

y = largestBST(root->right, rightMin, rightMax, size,bstRoot);

if(x==-1 || y ==-1)

return -1;

if(x==0)

{

leftMax = root->data;

leftMin = root->data;

}

if(y==0)

{

rightMin = root->data;

rightMax = root->data;

}

if(root->data < leftMax || root->data > rightMin)

return -1;

min = leftMin;

max = rightMax;

if(x+y+1 > size){

size = x+y+1;

bstRoot = root;

}

return x+y+1;

}

http://www.librethinking.com/2013/09/find-largest-binary-search-tree-in-tree.html

public static class TreeNodeHelper {


TreeNode node;


int nodes;


Integer maxValue;


Integer minValue;


boolean isBST;

public TreeNodeHelper() {}




public TreeNodeHelper(TreeNode node, int nodes, Integer maxValue, Integer minValue, boolean isBST) {


this.node = node;


this.nodes = nodes;


this.maxValue = maxValue;


this.minValue = minValue;


this.isBST = isBST;


}      


}


 


public static TreeNodeHelper getLargestBST(TreeNode tree) {


if (tree == null) {


return new TreeNodeHelper(null, 0, null, null, false);


}


if (tree.left == null && tree.right == null) {


TreeNodeHelper helper = new TreeNodeHelper(tree, 1, tree.value, tree.value, true);


return helper;


} else {


TreeNodeHelper leftBst = getLargestBST(tree.left);


TreeNodeHelper rightBst = getLargestBST(tree.right);            


 


if (!(rightBst.isBST && rightBst.minValue > tree.value)) {


rightBst.isBST = false;


}


 


if (!(leftBst.isBST && leftBst.maxValue < tree.value)) {


leftBst.isBST = false;


}


 


if (leftBst.isBST && rightBst.isBST) { 


return new TreeNodeHelper(tree, rightBst.nodes + leftBst.nodes + 1, rightBst.maxValue, leftBst.minValue, true);


} else if (tree.left == null && rightBst.isBST) {


return new TreeNodeHelper(tree, ++rightBst.nodes, rightBst.maxValue, tree.value, true);


} else if (tree.right == null && leftBst.isBST) {


return new TreeNodeHelper(tree, ++leftBst.nodes, tree.value, leftBst.minValue, true);


} else { 


return leftBst.nodes >= rightBst.nodes ? leftBst : rightBst;


}


}


}

The largest BST may or may not include all of its descendants.
https://github.com/xiaoningning/algorithm/blob/master/PuzzleCoding/src/LargestBSTSubtree.java
    public static class LargestBST {
        public Node node;
        public int maxNode;
        public int min;
        public int max;
    }
    // The largest BST must include all of its descendants.
    public static LargestBST largestBSTSubtree2(Node node) {
        if (node == null)
            return null;
        if (node.left == null && node.right == null) {
            return new LargestBST(node, node.size(), node.value, node.value);
        }

        LargestBST leftNode = largestBSTSubtree2(node.left);
        LargestBST rightNode = largestBSTSubtree2(node.right);

        if (leftNode != null && rightNode != null) {
            if ((node.value > leftNode.max && node.left == leftNode.node)
                    && (node.value < rightNode.min && node.right == rightNode.node)) {

                LargestBST bst = new LargestBST(node,
                        leftNode.maxNode + rightNode.maxNode + 1,
                        leftNode.min,
                        rightNode.max);

                return bst;
            } else {
                return (leftNode.maxNode > rightNode.maxNode) ? leftNode : rightNode;
            }
        } else if (leftNode != null) {
            if (node.value > leftNode.max && node.left == leftNode.node) {
                return new LargestBST(node, leftNode.maxNode + 1, leftNode.min, node.value);
            } else {
                return leftNode;
            }

        } else if (rightNode != null) {
            if (node.value < rightNode.min && node.right == rightNode.node) {
                return new LargestBST(node, rightNode.maxNode + 1, node.value, rightNode.max);
            } else {
                return rightNode;
            }
        }
        return null;
    }
http://www.librethinking.com/2013/09/find-largest-binary-search-tree-in-tree.html
https://gist.github.com/cvielma/6643658

public static class TreeNodeHelper {


        TreeNode node;

int nodes; //number of nodes


Integer maxValue;


Integer minValue;


boolean isBST;    

}

public static TreeNodeHelper getLargestBST(TreeNode tree) {


if (tree == null) {


return new TreeNodeHelper(null, 0, null, null, false);


}


if (tree.left == null && tree.right == null) {


TreeNodeHelper helper = new TreeNodeHelper(tree, 1, tree.value, tree.value, true);


return helper;


} else {


TreeNodeHelper leftBst = getLargestBST(tree.left);


TreeNodeHelper rightBst = getLargestBST(tree.right);            


 


if (!(rightBst.isBST && rightBst.minValue > tree.value)) {


rightBst.isBST = false;


}


 


if (!(leftBst.isBST && leftBst.maxValue < tree.value)) {


leftBst.isBST = false;


}


 


if (leftBst.isBST && rightBst.isBST //? && rightBst.minValue > tree.value && && leftBst.maxValue < tree.value ) { //Both leaves are BST and BST is satisfied with current root

return new TreeNodeHelper(tree, rightBst.nodes + leftBst.nodes + 1, rightBst.maxValue, leftBst.minValue, true);


} else if (tree.left == null && rightBst.isBST) { //Only right leaf and BST is satisfied with current root


return new TreeNodeHelper(tree, ++rightBst.nodes, rightBst.maxValue, tree.value, true);


} else if (tree.right == null && leftBst.isBST) {//Only left leaf and BST is satisfied with current root.


return new TreeNodeHelper(tree, ++leftBst.nodes, tree.value, leftBst.minValue, true);


} else { //No BST is satisfied with current root


//At this point is determined that no BST can include current node, so we return


//the leaf that had the largest BST until now (if there was one)


return leftBst.nodes >= rightBst.nodes ? leftBst : rightBst;


}


}


}

Read full article from Find the largest BST subtree in a given Binary Tree | GeeksforGeeks