We have to write a program to find the largest binary search tree (BST) in a given binary tree.
A given tree is BST if the value of node is greater than the value of its left child and smaller than the value of its right child.
We will use top-down approach for solving this. We will traverse the whole tree. At every node we will check if the subtree is BST or not. If the current tree is BST then we found the largest BST. If not, then we have to check the whether left or right subtree is BST or not. If only one tree is BST then we will return that subtree. If both left and right subtrees are BST, then we will return the larger of the two.
Example:
60
/ \
50 90
/ \ / \
40 55 70 100
/ / \
80 200 150
In the above binary tree, the whole tree is not BST because left child of 70 is 80 (>70) and also left child of 100 is 200 (>100).
Largest BST in the above example is:
50
/ \
40 55
The code will return 3 as there are three nodes in the largest BST.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
// C++ program to find largest binary search tree in a Binary Tree
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int data) // Constructor that makes a new node
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
// This function finds the maximum size of the largest BST.
// If the tree is BST then this function returns the size of the tree
int findBST(node* node, int *minn, int *maxx, int *maxSize, bool *isBst){
// Base Case
if(node == NULL){
*isBst = 1;
return 0;
}
int lSize, rSize; // Stores the size of left and right subtree.
int mi = INT_MAX;
bool flag1 = 0; // Flag for left subtree. It stores 1 if left subtree is BST.
bool flag2 = 0; // Flag for right subtree. It stores 1 if right subtree is BST.
*maxx = INT_MIN;
lSize = findBST(node->left, minn, maxx, maxSize, isBst); // recursive call for left subtree
// checking if left subtree is BST or not
if (*isBst == 1 and node->data > *maxx)
flag1 = 1;
mi = *minn;
*minn = INT_MAX;
rSize = findBST(node->right, minn, maxx, maxSize, isBst); // recursive call right subtree
// checking if right subtree is BST or not
if (*isBst == 1 and node->data < *minn)
flag2 = 1;
if (mi < *minn)
*minn = mi;
if (node->data < *minn)
*minn = node->data;
if (node->data > *maxx)
*maxx = node->data;
// If right and left subtrees are BST, then return the size of the tree.
if(flag1 and flag2){
if (lSize + rSize + 1 > *maxSize)
*maxSize = lSize + rSize + 1;
return lSize + rSize + 1;
}
else{
// If tree is not BST
*isBst = 0;
return 0;
}
}
int main()
{
node *root = new node(60);
root->left = new node(50);
root->right = new node(90);
root->left->left = new node(40);
root->left->right = new node(55);
root->right->left = new node(70);
root->right->left->left = new node(80);
root->right->right = new node(100);
root->right->right->left = new node(200);
root->right->right->right = new node(150);
int minn = INT_MAX, maxx = INT_MIN;
int maxSize = 0; // stores maximum size of the BST
bool isBst = 0; // If tree is BST then we store 1 in it, otherwise 0.
findBST(root, &minn, &maxx, &maxSize, &isBst); // values are passed by reference
cout<<"Size of the largest BST is: "<<maxSize;
return 0;
}
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Output : 3
Time Complexity : O(n)
n is the number of nodes in the given binary tree
