Largest Binary Search Tree in BT | C++ Placement Course | Lecture 28.10

[@amayatre3558]

That's what we all wanted from start ❤️❤️Make videos of longer duration but explain properly. This was best, perfectly explained. ❤️

[@willturner3440]

Only and Only in apna college, hats off to the great ma'am

[@krishnanarwani8105]

Bohot hi pyara concept...Maza aa gya... Kya toh samjhaya he...Waah

[@ShubhivDogra]

this course made me answer all the interview qns asked in my college campus placenment -- 14lpa-gap

[@sakshamjain3775]

@Shubiv Dogra what were the questions based upon??

[@ShubhivDogra]

@@sakshamjain3775 based on stacks and linked lists..

[@rahul_ji21]

@@ShubhivDogra congrats

[@sumitKumar-pf9xo]

Congo bro 🤗🤗🤗

[@chanduchandrakanth5131]

Bro Which clg r u from?

[@sudhanwapande2040]

Bohot aala samjhaya aapne.. itna tough concept ko easy kardiya🙏

[@PankajSingh-vi3fy]

love that music of keyword.. so satisfying 😌

[@upasanapan1790]

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

[@beenaasha506]

Great explanation

[@satyam5036]

Who noticed this is dynamic programing on trees to avoid repetition

[@lokeshdulani6035]

fucking awesome far better explanation than content available at other sites

[@avronilbanerjee5302]

didi you are a legendary person !

[@adityabhandari6688]

great explanation mam, this is what is called perfect explanation

[@devilronak7262]

op, heads off to this video, what a great explanation, jod or what?

[@devilronak7262]

@@utkarshverma2604 😂😂😂

[@its_neel_ok]

@@devilronak7262 ya toh pubg wala ha kaya.....xD

[@devilronak7262]

@@its_neel_ok 😂

[@its_neel_ok]

@@devilronak7262 xD

[@devilronak7262]

@@its_neel_ok xD

[@rajveerbari791]

COOKING 🍳 AND SERVING(TEACHING) US AT THE SAME TIME🤣 We can hear 👂 the cooper's whistle behind.

[@hustlewithVaibhav]

Thank you 🙏🙏

[@shreyankshrestha9274]

bahut sahi ❤❤

[@Zeno_Yoru]

Vaiya. Lecture 28.9???

[@SubhamKumar-fr7gw]

paikhana kare me t ek number bate e log

[@NiteshSingh5375]

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.

[@nazeershaik9812]

#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

[@ritwickrana3255]

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

[@tarunbisht8016]

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.

[@naiyerabbas6481]

Yeah!! I was also thinking about it.. We don't need min and max

[@avronilbanerjee5302]

@@naiyerabbas6481 no you have to check what if the left or right child is NULL ?? then the min would be different

[@letsdoeverythinginoneweek9398]

IF ROOT ==NULL IT NOT ONLY SATISFY THE NO NODE CONDITION BUT IT ALSO SATISFY THE LEAFT NODE CONDITION

[@pekkingjackal1180]

Yes,you are right but I cannot understand the logic, can you please explain it?

[@SagarSagar-ym5wx]

very good

[@maneshwarsingh8688]

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.

[@sameeryadav8857]

yes i also think so... that was not necessary...

[@piyushlohiya1977]

I also thought that and it is correct!! What she said is just unnecessary

[@nishantchauhan2596]

@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)

[@adarshdubey1784]

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

[@Subhankar415]

@@adarshdubey1784 There is a need. Look at the comment above

[@hardikagarwal7652]

curr.min and curr.max ko if statement ke bahar hona chahiye

[@vinaydangayach386]

yes but dont know why this code is not giving error?

[@chirag-sg4kd]

same doubt but agr bahar rakh rahe hai to ans 1 aa raha hai

[@sanketbhagat1222]

@@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..

[@piyushlohiya1977]

@@sanketbhagat1222 if ke bahar bhi aur andhar bhi hona chahiye

[@TUSHAR-mj1en]

@@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

[@vaibhavbelekar4653]

Student : Notes de de Thakur......

[@adarshdubey1784]

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 ..?

[@cenacr007]

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.

[@namangoyal8477]

Excellent

[@AdarshSingh-on5fy]

#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

[@Saurabh-gg9lv]

int max and int min

[@santoshbhupati3579]

Thankyou

[@royal_bettiah22]

Nice Sir

[@hardikagarwal7652]

15 and 30 will not be a BST

[@AmrutanshuMishra-dp1mf]

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 ??????

[@uxxrhiiikgfdsdvhj]

exactly my point

[@sanjayswami1155]

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

[@pulkitmittal584]

yes

[@sanketbhagat1222]

Mam, please correct that, curr.min & curr.max if ke bahar hona chahiye..

[@piyushlohiya1977]

Kyo?

[@Subhankar415]

Does not make a difference anyways. for the other case, you will not be using the values anyways

[@shauryashekharsahu7485]

Aman bhaiya unacademy m aap padhayenge ya nhi plz bataiye mai bura fas gya hu

[@vansh6368]

🙂😂

[@omkarmhaske8120]

comment 0

[@willturner3440]

At last why we are not set the value of curr. Max and curr. Min

[@shubhamgoel3998]

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; }

[@divyanshugautam2304]

cant we do it like take the inorder then the largest sorted sub array of preorder is no of nodes of largest bst

[@adityaagarwal3511]

why we haven't used public in the structure info

[@pranjalrajput2886]

Lecture 28.9 is Missing

[@its_neel_ok]

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

[@anonymouspromax]

28.9 lecture??

[@lavyadav2396]

I think on line no. 41 there will be change ----->>> curr.ans = max ( curr.size , max ( leftinfo.ans , rightinfo.ans ) );

[@Rohan-ov3fr]

Bhai kuch samjh bhi aaya kuki mugje ek baar me kuch ni aaya 🥺🥺

[@depression_plusplus6120]

Itna easily samjhaya hai fir bhi agar samaj na aaya plz revise kare apni basics

[@AlokSingh-jw8fr]

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???????

[@vasukotadiya6235]

In C++ we can make constructors in structure... You are right but in C language

[@adityabhandari6688]

bro watch full video, it was an error which she corrected at the end

[@NareshKumawat-w9z]

this is not applicable in all conditions

[@PegasiuuuS]

Can't we just find inorder traversal and check for size of longest increasing sub array in that inorder traversal

[@azeezmoiz9195]

It doesnt work that way take a sample input from GFG and dry run your logic

[@tarunbisht8016]

@@azeezmoiz9195 No, i think it will work perfectly just space complexity o(n) ho jayega

[@tarunbisht8016]

@@azeezmoiz9195 even we can do it without using any vector also

[@promphotos5403]

@@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.

[@SagarSagar-ym5wx]

ma'am please send the source code

[@jaydalsaniya6986]

Avaaz bohot Dabi dabi lagg rahi hai

[@Priyanka_Aarna]

First one 😊

[@tanmayjain8542]

1st comment

[@ayushbankia9004]

Anyone 12th pcm?

[@pathikshah]

JEE me kitne aaye ?

[@ayushbankia9004]

@@pathikshah bhai bahut kharab aye. 96.2.

[@pathikshah]

Toh padhna JEE ka, idher kya kr rha hai? DSA college me bahut time milega..

[@girishporwal5183]

@@pathikshah lol

[@piyushbansal9716]

@@pathikshah LMAO