Largest Binary Search Tree in BT | C++ Placement Course | Lecture 28.10
ฝัง
- เผยแพร่เมื่อ 19 ก.ย. 2024
- Complete C++ Placement Course (Data Structures+Algorithm) : • C++ Full Course | C++...
Telegram: t.me/apnikaksh...
Instagram: / dhattarwalaman
Notes of this Lecture:
this course made me answer all the interview qns asked in my college campus placenment -- 14lpa-gap
@Shubiv Dogra what were the questions based upon??
@@sakshamjain3775 based on stacks and linked lists..
@@ShubhivDogra congrats
Congo bro 🤗🤗🤗
Bro Which clg r u from?
That's what we all wanted from start ❤️❤️Make videos of longer duration but explain properly. This was best, perfectly explained. ❤️
Only and Only in apna college, hats off to the great ma'am
Bohot hi pyara concept...Maza aa gya... Kya toh samjhaya he...Waah
struct Info {
int size;
int max;
int min;
int ans;
bool isBST;
};
if(root==NULL){
return{0,INT_MIN,INT_MAX,0,true};//will only come here if already traversed left and right / left is NULL so we put INT_MAX in rightInfo.min as null means it has to be greater than root in all cases and we put INT_MIN in leftInfo.max as null means it has to be less than root in all cases. LOOK ORDER IS REVERSED FOR max and min AND INT_MIN and INT_MAX.
}
p.s IT took me 3 days to realise this.sed life
Great explanation
love that music of keyword.. so satisfying 😌
Vaiya. Lecture 28.9???
Bohot aala samjhaya aapne.. itna tough concept ko easy kardiya🙏
op, heads off to this video, what a great explanation, jod or what?
@@utkarshverma2604 😂😂😂
@@devilronak7262 ya toh pubg wala ha kaya.....xD
@@its_neel_ok 😂
@@devilronak7262 xD
@@its_neel_ok xD
fucking awesome far better explanation than content available at other sites
Who noticed this is dynamic programing on trees to avoid repetition
great explanation mam, this is what is called perfect explanation
Thank you 🙏🙏
I don't think there is any need to check whose value is minimum left info, right info, and current root value, cause it's obvious that left info's min value will be min and if it is not the case then it's not a bst.
Yeah!! I was also thinking about it.. We don't need min and max
@@naiyerabbas6481 no
you have to check what if the left or right child is NULL ?? then the min would be different
I think last statement spoken by tutor is not correct. Ans=2 because of max. BST found is due to 20 & 5 but not 15&30. we can not take partial(one side either left or right) Binary tree to accept it as a BST.
COOKING 🍳 AND SERVING(TEACHING) US AT THE SAME TIME🤣
We can hear 👂 the cooper's whistle behind.
#include
#define ll long long
#define loop(i,n) for(int i = 0; i < n; i++)
#define loop1(i,n) for(int i = 1; i left);
vector rt = help(root->right);
vector curr (5,0);
curr[3]=1+lt[3]+rt[3];
if(root->data>lt[1] && root->datadata,lt[0]);
curr[1]=max(root->data,rt[1]);
curr[2]=1;
curr[4]=curr[3];
return curr;
}
curr[4]=max(lt[4],rt[4]);
return curr;
}
int largestBST(Node* root){
return help(root)[4];
}
int main()
{
Node* root;
cout
curr.min and curr.max ko if statement ke bahar hona chahiye
yes but dont know why this code is not giving error?
same doubt but agr bahar rakh rahe hai to ans 1 aa raha hai
@@chirag-sg4kd nahi, bahar rakha to 2 aa raha hai. agar 20 to 10 se replace kiya jai to 4 ata hai, means min, max ko if ke bahar rakhne se sahi output aa raha hai..
@@sanketbhagat1222 if ke bahar bhi aur andhar bhi hona chahiye
@@vinaydangayach386 dekh bhai min max ko update karne ka koi fayada nhi h
kyuki jab isbst false h to bade wale if condition bhi false hoga
uka min max kabhi bhi compare hoga hi nhi bro
aur uske karn ab uss node to milakar kabhi bhi answer nhi banega
I have doubt on line no.37...if current node is BST then on line no.38 the minimum value of current node should be "minimum value from left subtree", as we mentioned left subtree is also bst ..?
it's a recursive approach, think in that way, will your logic work in case of leaf nodes and nodes with only right subtree. think for one node, the last one and slowly move upwards, don't pick random node and only think about it.
19:55 Wouldn't curr.min = leftInfo.min and curr.max= rightInfo.max directly be applicable instead of comparing with root->data since the said root is already validated to be a BST! So leftInfo.min would always be less than root->data (heck, root->data is greater than leftInfo.max too) and similarly for curr.max also.
yes i also think so... that was not necessary...
I also thought that and it is correct!! What she said is just unnecessary
@Maneshwar Singh No brother we need to do that. Consider a case where a node has only right subtree than in that case curr.min=leftInfo.min will not work because now curr.min is root->data.so we need to that.
Though that whole line is not required this will do the work
curr.min=min(leftInfo.min , root->data)
Bro , I asked same doubt in comment section and then I started to search if someone has encountered same doubt or not, then I found you ....So, I think There is no need to write that lengthy stuff
@@adarshdubey1784 There is a need. Look at the comment above
as i am moving forward in this course no. of likes are and views are decreasing
i guess they are not able to continue in this journey
i think there was no need to right extra conditions for the leaf nodes and it will automatically get calculated , anyone correct me if I am wrong
yes
didi you are a legendary person !
bahut sahi ❤❤
IF ROOT ==NULL
IT NOT ONLY SATISFY THE NO NODE CONDITION BUT IT ALSO SATISFY THE LEAFT NODE CONDITION
Yes,you are right but I cannot understand the logic, can you please explain it?
i had a doubt when we are updating the value of our curr minimum and maximum cant we simply just say curr.min=left.min and curr.max=right.max as we are checking if the current node is a bst before this ??????
exactly my point
Excellent
Aman bhaiya unacademy m aap padhayenge ya nhi plz bataiye mai bura fas gya hu
🙂😂
Thankyou
15 and 30 will not be a BST
Mam, please correct that, curr.min & curr.max if ke bahar hona chahiye..
Kyo?
Does not make a difference anyways. for the other case, you will not be using the values anyways
Student : Notes de de Thakur......
very good
paikhana kare me t ek number bate e log
cant we do it like take the inorder then the largest sorted sub array of preorder is no of nodes of largest bst
Can anyone please explain me at 12:24 di has made a constructor in structure how's it possible constructors are to be made in classes???????
In C++ we can make constructors in structure... You are right but in C language
bro watch full video, it was an error which she corrected at the end
Nice Sir
At last why we are not set the value of curr. Max and curr. Min
#include
using namespace std;
class node{
public:
int data;
node *left;
node *right;
node(int d){
data=d;
left=NULL;
right=NULL;
}
};
class bst{
public:
int size;
int max;
int min;
int ans;
bool isbst;
};
bst largestbst(node * root){
// root is null and size is 0
if(root==NULL){
return {0,INT_MAX,INT_MIN,0,true};
}
// leaf node condition
if(root->left== NULL and root->right ==NULL){
return{1,root->data,root->data,1,true};
}
bst left=largestbst(root->left);
bst right=largestbst(root->right);
bst curr;
curr.size=(1+left.size+right.size);
if(left.isbst and right.isbst and left.maxdata and right.min>root->data){
curr.min=min(left.min ,min(right.min,root->data));
curr.max=max(right.max ,max(left.max,root->data));
curr.ans=curr.size;
curr.isbst=true;
return curr;
}
curr.ans=max(left.ans,right.ans);
curr.isbst=false;
return curr;
}
int main(){
/*
15
/ \
20 30
/
5
*/
node *root=new node(24);
root->left=new node(20);
root->right=new node(30);
root->left->left=new node(5);
cout
int max and int min
why we haven't used public in the structure info
what is the meaning of ans in the list when explaining isn't it the size of the largest BST...then how come it is equal to the root??? I didn't understand that
I think on line no. 41 there will be change ----->>> curr.ans = max ( curr.size , max ( leftinfo.ans , rightinfo.ans ) );
int largestBst(node *root,int *Max,int *Min,bool *isBst) {
if (root==NULL) {
*isBst = true;
return 0;
}
int lMax,lMin,rMax,rMin;
bool isBstLeft,isBstRight;
int left = largestBst(root->left,&lMax,&lMin,&isBstLeft);
int right = largestBst(root->right,&rMax,&rMin,&isBstRight);
*Max = root->data;
*Min = root->data;
*isBst = true;
if (isBstRight == false || isBstLeft == false) {
*isBst = false;
return max(left,right);
}
if (root->left!=NULL) {
if (lMax > root->data) {
*isBst = false;
}
else {
*Max = max(*Max,lMax);
*Min = min(*Min,lMin);
}
}
if (root->right!=NULL) {
if (rMin < root->data) {
*isBst = false;
}
else {
*Max = max(*Max,rMax);
*Min = min(*Min,rMin);
}
}
if (*isBst == false) {
return max(left,right);
}
return 1+left+right;
}
comment 0
2:20
4:10
this is not applicable in all conditions
Lecture 28.9 is Missing
28.9 lecture??
Can't we just find inorder traversal and check for size of longest increasing sub array in that inorder traversal
It doesnt work that way take a sample input from GFG and dry run your logic
@@azeezmoiz9195 No, i think it will work perfectly just space complexity o(n) ho jayega
@@azeezmoiz9195 even we can do it without using any vector also
@@tarunbisht8016 naah, we can have a case in which two bst subtrees can be combined to give a sorted subarray in a inorder traversal array.
Bhai kuch samjh bhi aaya kuki mugje ek baar me kuch ni aaya 🥺🥺
Itna easily samjhaya hai fir bhi agar samaj na aaya plz revise kare apni basics
ma'am please send the source code
Avaaz bohot Dabi dabi lagg rahi hai
First one 😊
1st comment
Anyone 12th pcm?
JEE me kitne aaye ?
@@pathikshah bhai bahut kharab aye. 96.2.
Toh padhna JEE ka, idher kya kr rha hai? DSA college me bahut time milega..
@@pathikshah lol
@@pathikshah LMAO