9.a) Largest bst in binary tree || Binary Search Tree || Data Structure

In this video, I have discussed about finding the largest bst in binary tree data structure.

The algorithm used is, for each node, we calculate largest bst in its left and right subtree and then check whether a bst can be formed with current node as root of bst and then return the largest of all.

Practice questions:

I hope you liked my video, do subscribe to my channel to get the updates of my latest uploads.

#bst #binarysearchtree #binarytree #datastrucuture #algorithm #interviewquestions #placement #internship #faang

[b_anukuldewangan]

C++ code :

class bst{
public:
bool isbst;
int size;
int min;
int max;
};


class Solution{
bst Ans(Node * root )
{
if(root==NULL)
{
bst b={true, 0, INT_MAX, INT_MIN};
return b;
}

bst l=Ans(root->left);
bst r=Ans(root->right);

if(l.isbst && r.isbst && l.max<root->data && r.min> root->data)
{
bst b={true, 1+l.size+r.size, min(root->data, l.min), max(root->data, r.max)};
return b;
}

bst b={false, max(l.size,r.size),-1,-1};
return b;
}
public:
/*You are required to complete this method */
// Return the size of the largest sub-tree which is also a BST
int largestBst(Node *root)
{

bst b=Ans(root);
return b.size;

}

[mahipalsingh-yojt]

you made such a hard que very easy for me. Thanks.
code in java:----
class Solution{
static class Data{
boolean result;
int max;
int min;
int treesize;
Data(boolean r, int mi, int ma, int size){
result = r;
min = mi;
max = ma;
treesize = size;
}

}
// Return the size of the largest sub-tree which is also a BST
static int largestBst(Node root)
{
return find(root).treesize;


}
static Data find(Node root){
Data x;
if(root == null) {
x = new Data(true, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
return x;
}
Data left = find(root.left);
Data right =find(root.right);

if(left.result && right.result && root.data>left.max && root.data<right.min){
x = new Data(true, Math.min(left.min, root.data), Math.max(root.data, right.max), 1+left.treesize+right.treesize);

}
else{
x = new Data(false, -1, -1, Math.max(left.treesize, right.treesize));
}
return x;




}



}

[SubhamKumar-]

struct bst
{
bool isBST;
int size;
int min;
int max;
};

bst check(Node *root)
{
if(!root)//base condition
{
bst b={true, 0, INT_MAX, INT_MIN};
return b;
}

bst traversal
bst right=check(root->right);

if(left.isBST && right.isBST)//operation on node
{

if(left.max<root->data && in left should be less than node and minimum in right should be greater than node
{
bst b={true, 1+left.size+right.size, min(root->data, left.min), max(root->data, right.max)};
return b;
}

}
bst b={false, max(left.size, right.size), -1, -1};//if not bst
return b;
}

int largestBst(Node *root)
{
bst x=check(root);
return x.size;
}

[sudiptahalder]

excellent approach and very nice explanation bro!! 🔥🔥

[aakash]

great video I have one more solution, will it work?
so we have a binary tree and we need to find the largest bst

Can I do the inorder traversal and store that in an array. Now in that array, I just need to find the largest subarray which is sorted and that will be our answer?
Will this solution work?
please comment.

[parasdawar]

Hi Kashish, Thanks for this amazing playlist. I have one doubt in this prob, why are we updating the size in false case and why not keeping a pass by reference variable and check max size in true scenarios only ? Thanks.

[acxd]

Bhai github gist pe code bhi share kar diya karo

[sharuk]

bhai code b shre kr dia kro github or another plateform

[abhiprayadash]

Bhai mast explanation keep it on!!ur teaching style is amazing.

[shivamdalania]

Didn't got anything, seems like u r self confused and not able to explain, please explain properly.