L53. Largest BST in Binary Tree

[@takeUforward]

This is the last video of this series. I hope you enjoyed this. Just a small request: “Please share the series, also you can tag me at Linkedin if you want a give a review for this series, this will do me a world of good” Thankyou 🙏🏻

[@yash0270]

Thanks for creating this series.

[@akhilesh59]

Thank you Bhaiya for this Wonderful series. It was the best DSA based series for me so far. I have already recommended this to all my friends. Now going to start the Graph series 😁..

[@sejalrai7358]

completely Lovedd this seriess!! thanks a lotttt

[@krishnarajs929]

Thanks bro , It was absolutely great...

[@vaibhavkumar526]

Hi I feel like the base case value is incorrect, lets say when root is Null, then my tuple returned should have maxNode as -infinity and minNode as +infinity. Then only lets say for a leaf node we can have a value of 1, as a single node is also a BST. Please check this. I tried dry running the code and it didn't work, so I thought I should share this. Well I might be wrong, so please cross verify. I can prove this, lets say, the leaf node is 10, so from the left side the max value would be -infinity and from the right side min value would be +infinity and hence the condition -infinity < 10 and 10 < + infinity would satisfy

[@subodh.r4835]

CONGRATS to everyone else who successfully completed this playlist!

[@kushagraahire1871]

Did you get a job after learning DSA?

[@ultimategyani6412]

​@@kushagraahire1871 yes I got a full stack developer internship in Lockheed Martin( remote ). They asked me two DSA ques in technical round Print spiral matrix Lowest common subsecuence using DP

[@kushagraahire1871]

@@ultimategyani6412 congratulations

[@ultimategyani6412]

@@kushagraahire1871 thanks brother

[@horccruxxxop4184]

@@ultimategyani6412 what were your projects?

[@arpanbanejee5143]

Completed the entire FREE KA TREE series! Learnt a lot! Thank you Striver for putting up such quality content!

[@bhargav1811]

11:27 Minimal will be 30 and not 40 !! Thank you striver for this series!! Helped me alot !!

[@Area-fd8ht]

​@@namashsharma7550tum toh lodu ho fir..😂

[@PrinceTripathi-j7u]

Completed the Tree series in 10 days. Thank you STRIVER for making such a quality content .

[@abdulrazzak2934]

finally completed this amazing free ka tree series and now im taking a break then soon i'll start the next your graph series thanks alot striver for amazing explanation,efficient code ,time complexity an all.thank you so much

[@vaishnavigour5777]

completed this series today! THANKYOU STRIVER for making such a quality content . Really helped a lot . It took me 6 days to complete this series . It was worth it.

[@kartiksrivastava3897]

currently watching the last video it took me 14 days.

[@codding32world50]

like how many videos per day

[@parthsalat]

Did you save/write the codes somewhere, like in a notebook or notion? Because storing codes takes up a lot of my time.

[@vaishnavigour5777]

Yes @parth I have noted them down in a notebook...not the full code but just the pseudo code

[@parthsalat]

@@vaishnavigour5777 Great! After consulting my "smart" friends, I too have decided to save codes only for difficult questions. For normal questions, I'll just jolt them down in a paper.

[@shobhitshrivastav9775]

Today I have completed the Free Ka Tree series playlist .It took almost 21 days to complete this series from start to end .I really enjoyed the playlist and learn many new ways of solving tree questions ...thanku striver bhaiya for this top quality content always be thankful to you❤️❤️

[@sujoyseal195]

Correction : At 11:30 , the minimum for subtree with root=40 is 30 not 40 . Please provide an edit at this juncture

[@abhimanyuraizada7713]

It made my head spin

[@interesting.finds.1857]

true;

[@Now_I_am_all_fired_up]

True Bhai yrr mera dimag kharab ho gya .......

[@vishichaurasiya4427]

@@Now_I_am_all_fired_up L lag gaye the mere 😓

[@piyushlohiya1977]

searching for this comment

[@aaqilkrishna8840]

Just completed this playlist and I would highly recommend it to anyone wanting to learn how to solve Binary Tree and Binary Search Tree based problems from scratch. Thank you for this valuable content !! Cheers ✌❤

[@AkashDeep-jp1ts]

The hardest tree question I came across but thanks to you, now it's completely clear!!

[@noone-pn7yu]

completed whole playlist today, thank striver

[@taranjotsingh7780]

Completed the entire series today. Feeling much more confident now. Thank you very much Stiver! 😃

[@Dontpushyour_luck]

completed the entire tree series. Enjoyed a lot! thank you for all the content striver!

[@captcha14]

Earlier trees and graphs haunt me. Completed this playlist and now questions are solvable. Thank you striver.

[@closetoheart6120]

bhai are these playlist to understand concept easily ?? and is whole DSA complete here ?

[@pushkarchoudhary8276]

@@closetoheart6120 tree playlist are awesome u can follow this according to me

[@aadityakhetan956]

A great series to learn tree from scratch. Thanks for top notch content. It was really very helpful.

[@Tahirkhan-hv3jn]

**important** if someone is confused while doing dry runwith the solution and example then consider this, There is issue in naming of variables in the code, even though things work well. The maxNode should be replaced by minNode and vice-versa.

[@lifegood6401]

It is such a Great Series. More power to Striver. You are the superhero of students like us.

[@_CSE_PRATHISWARANGR]

Just completed your amazing tree series Striver and thanks for making such a wonderful series for free :)

[@ashishpradhan6250]

another playlist completed.. thanks for bringing a change in other's lives

[@jagjiwanchimkar8106]

Mistake at 11:28 , For 40, smallest will be 30 not 40

[@ashoksrinivasan4627]

S

[@rishabhgupta1222]

Just completed the Tree series playlist....absolutely mindblowing content with highest level of perfection !!!!

[@iamnoob7593]

Done with free ka tree series. A big thank you striver , I taught i knew trees very well , But when i watched these videos , I had not known most of it.

[@divyamgupta-t3i]

Can this approach work, not wrt TC, but the intuition only ? 1. Find Inorder of binary tree and store it in vector 2. Find the largest sorted substring in that vector Considering each element in tree is unique.

[@selvamani.kannan]

yes, it should work. length of longest increasing sub array

[@SameerRehan-tt4lh]

no

[@dank7044]

It won't work,because we need to return a node as an ans. so the ans would be the complete tree,originating from that node,you cant selectivel keep or exclude any of its child,by your method, you might do this

[@ashutoshpandey904]

Finally, Completed this entire series and learnt a lot! It took me around 3 weeks to complete this series and it's totally worth it. Thank you Striver for such quality content, Really helped me a lot !❤❤

[@Manishgupta200]

This series is superb. Understood all series problem with proper Dry run and solved in multiple ways from Brute to Better to Optimal. Apart from that solved logical tree problem by myself.. Digonal traversal, Path Sum, Sum tree.. and going on..

[@tejassrivastava6971]

solution with cam makes more easier to understand the concept. Thanks!

[@arghya_0802]

Completed the entire Tree Series. The best one without a doubt!! Finished all the questions & will probably do a couple more. The next destination is DP !!

[@priyanshkumar17]

This is one of the best videos of the playlist !!! Thanks Striver bhaiya :)) You made trees easier to understand & visualize...

[@FTWaditya]

**Correctionss if(root==NULL) return {INT_MIN,INT_MAX,0}; if(root->data>left.mx && root->datadata,right.mx),min(root->data,left.mn),1+right.n+left.n}; } else { return {INT_MAX,INT_MIN,max(left.n,right.n)}; }

[@mohammedraiyaan-bt6iy]

Thanks sir , Because of you another topic of dsa is completed.

[@____Akash__]

Time Complexity O(N^2) and sc O(1) class Solution{ public: //the brute force approach is first i'll check for every node if this node // is a root of a bst or not if this node contains bst then we cnt the size //time complexity O(N^2) bool isValidBST(Node* root,int min, int max){ if(root == NULL) return true; if(root->data < min || root->data > max){ return false; } return isValidBST(root->left, min, root->data) && isValidBST(root->right, root->data, max); } int countNode(Node* root){ if(root == NULL) return 0; if(!root->left && !root->right) return 1; int left = countNode(root->left); int right = countNode(root->right); return left + right + 1; } void checkNode(Node* root, int &maxi){ if(root == NULL) return; if(!root->left && !root->right) return; if(isValidBST(root,INT_MIN,INT_MAX) == true){ int cnt = countNode(root); maxi = max(cnt, maxi); } checkNode(root->left, maxi); checkNode(root->right, maxi); } int largestBst(Node *root) { int maxi = 1; checkNode(root, maxi); return maxi; } };

[@saurabhgautam2697]

Completed the whole series ,I was kindaa slow ,took me 3 weeks-1 month,but understood the concepts very well ,as you always say straight into the mind Thankyou bhaiya

[@AngadSingh97]

Hi everyone The link from the SDE SHEET links to Maximum Sum BST in Binary Tree, whereas Striver has solved for Largest BST in Binary Tree. I did not read the question description correctly and was using the approach for the wrong question. Please be careful so that you don't waste 30 minutes like I did, debugging the code and wondering why it's not working. Good to reach the end of Tree Series, thank you Striver bhai. Now on to Graph and DP Problems : ).

[@HEMANTPORWAL-t7d]

495k to 137k itself speaks many things well done striver bhaiya

[@madhu_mohanreddy]

630k*

[@pavannettam8968]

The playlist was really helpful to understand trees, thank you so much @striver. I'm sure this is the best tree playlist in the market.

[@fakegmail3051]

code is not working bro

[@gouravkushwaha3001]

Completed this amazing free ka tree series today

[@abhijeetanand3443]

woho finally reached here, thankyou so much striver (Sir/Bhaiya) for this playlist. Many will come through all videos till here and each time you will be blessed by tons 🙌🤩

[@tanmaychaudhary2801]

In starting i have got fear from tree topic...and vertical order traversal topic was demotivating for me because at that time I was thinking this(tree and DSA) is not for me....but I continued it and striver bhaiya made it very easy to understand all the topics and now I am feeling very much familiar with this topic...now I am able to think for solutions by myself....thanks a lot striver bhaiya...❣️💫🙌😊🙏

[@LBK3]

Whole tree series is absolutely amazing used to have a lot of confusion on trees and pointers used in them... Completely cleared thanks alott Striver❤

[@sunnykumarsingh7039]

Today complete the SDE sheet. This was the last question I attempted. Yeah, the order in which I did was according to my comfort, Nevertheless, your content is LIFE-SAVER!!

[@ruturaj_dm]

I m not sure how is this solution a O(1) space complexity. We are creating and returning NodeValue object from each node. So for all the O(N) nodes we are returning a new object. If every object is assumed to take O(1) space then we have O(N)*O(1) = O(N) space.

[@pqrstwxyz1175]

Same doubt...did you get any explanation?...surely has to be O(N)

[@deepaksaini3986]

Completed successfully!! Now revision is the only thing to do !! and will do it!!

[@parthsalat]

Thanks for the series...I'd have never learnt BST if it wasn't for this series

[@varnit1975]

At size 4 the minimal should be min(40,30) = 30 not 40

[@HarshKumar-ip5nr]

Just an approach. What if we do inorder traversal and find the index of points that violate the increasing vector. Now, we have simultaneously calculated the size of each seperate BST in inorder traversal and return the max one. i.e. suppose the iteration was like: 2, 3, 4, 5, 1, | 6, 7, 8, 10, 12, 13, 9 | 20, 21.. The sizes are : 5, 7, 2 and we return 7. Any thoughts and code?

[@sarthakragwan5248]

This approch fails i also did this one

[@HarshKumar-ip5nr]

@@sarthakragwan5248 why, can you give some insight

[@dank7044]

@@HarshKumar-ip5nr It won't work,because we need to return a node as an ans. so the ans would be the complete tree,originating from that node,you cant selectivel keep or exclude any of its child,by your method, you might do this

[@arpitagupta5834]

In the first example, why isn't 10 included in the BST? (10,5,1,8)

[@Nikita-hv5jm]

finallyy completed the whole series....thanks a lot striver for such a wonderful series on tree...💫

[@vaibhav5269]

Hi Striver, Thanks for the free tutorials. I had a small doubt in this problem: If we just exclude 17 from the tree , the remaining tree is a BST, then the size would become 10. Why dont we solve it in this way, It is also a subtree right?

[@momilijaz271]

I am in love with this amzing content, definitely gonna follow all other playlists and striver's sheet. Can;t thank you enough for the great content.!

[@gouravkumar7459]

Thanks for this amazing playlist, though I knew trees and have done a lot of questions on it, still I wanted to learn new approaches, indeed I learned amazing approaches. Thanks again. :)

[@asit7456]

Could you please give notes of the tree series it is incomplete as the notes and the effective explanation makes the series effective.

[@rishabhgupta9846]

Completed the series in 2 weeks ,thank you Striver for such wonderful playlist.

[@anshumaan1024]

I took 3-4 weeks 🙂

[@prateek4-yearb.tech.chemic511]

I CAN CONFIDENTLY SAY THAT THIS IS THE ABSOLUTE BEST SERIES ON KZbin FIR TREES; LAST QUESTIONS WERE JUST TOP NOTCH . LOVED IT THANKS STRIVER .

[@MdArman_cs]

Finally i successfully completed the free ka tree series thanks striver bhaiya🧡

[@shirishprataya4602]

Finally completed this series. Thanks a lot Striver. You have helped a lot. This truly was the best tutorial on trees. 🔥🔥🔥

[@OmPrakash-kb2wq]

Thank you so much striver. I learnt a lot from this series. Earlier I have very low confidence in Tree and now after your series and practice I leave become very much confident in this portion.

[@gsmdfaheem]

Finally completed the entire Free Ka Tree Series....Thank you so much striver bhaiya for putting in all the efforts...You are the best.

[@sautramanivibhuti4597]

Finally completed Thanks striver bhaiya You owe my respect 📈❤️

[@gandhijainamgunvantkumar6783]

Completed this free ka series today in 4.5 days and it was amazing. Thank you striver bhaiya for providing this amazing content for free. :)

[@mohammedsaqib1250]

Itni jaldi 🥺

[@gandhijainamgunvantkumar6783]

@@mohammedsaqib1250 Yes as placement season is coming 😄

[@mohammedsaqib1250]

@@gandhijainamgunvantkumar6783 where r u from

[@gandhijainamgunvantkumar6783]

@@kms8320 Wow.. Amazing 👏👏

[@ayushdhiman8128]

ky ye series yaha samaapt hoti hai? Thank you for this free playlist ❤

[@huungryyyy]

bhai kitna pyaara soln likha hai 😍

[@AyushiSingh-iy5uf]

Merge two BSTs is missing in this series, please upload that too! Thanks in advance :)

[@stith_pragya]

Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@navyaposham-hx6ix]

I dont understand we can just exclude 14&17 right? If we include 15,16,18,19,20,30,40,50,60 we get a bst of size 9 and that can be our answer

[@abhinavpandey3356]

Is the complexity of brute is o(n^3) ie for passing every node to validate * validating *getting size if it is a valid BST ie o(n*n*n) ?please check

[@nadeemqwerty]

I am not sure but it seems to be wrong, what if subtree is not BST but follows the min max condition?

[@tusharnain6652]

d*mb

[@anmolgarg2951]

we are moving from bottom to top so every bottom node also following the MIN MAX condition so it must be BST as we are changing MAX to INT_MAX and MIN to INT_MIN whenever a single node is not satisfying the MIN MAX condition.. so it must be BST if it follows MIN MAX condition..

[@abhirupbasu3386]

Completed the tree series.Thanks for making this amazing tree series.

[@mdrehankhan3458]

Thanks man!! this series really helped me to solve tree problems which I found quite difficult while l solving tree questions.

[@DSRhymster]

Completed the whole tree series today.... Learnt alot thank you Striver the saviour 🥰🥰

[@sarthakkapoor3764]

How many more episodes left in the tree series?

[@shantipriya370]

completed the list.. thank you so much..

[@ArBond007]

Completed the playlist in 10 days, was an amazing journey...

[@mohdhammadsiddiqui7598]

With questions or without questions???

[@ArBond007]

@@mohdhammadsiddiqui7598 with questions

[@mohdhammadsiddiqui7598]

@@ArBond007 I'm currently on 35th video after completing playlist will start

[@ArBond007]

@@mohdhammadsiddiqui7598 nice

[@sanginigupta1312]

++

[@kashishsharma6809]

i like brute force also, putting memorization for sub branches.

[@sulakshsharma8520]

amazing explanation, thanks!

[@vivekchatterjee4001]

Completed the Series today, developed logic, and made notes, next is the Graph series. Journey never ends✌✌

[@dakshkalucha5408]

There is issue in naming of variables in the code, even though things work well. The maxVal should be replaced by minVal and vice-versa.

[@bhushanasutkar6135]

true

[@ayobrrr]

class Solution: def largestBst(self, root): def rec(node): if node: if not node.left and not node.right: return [True, node.data, node.data, 1] left = rec(node.left) right = rec(node.right) if left[0] and right[0] and left[2] < node.data < right[1]: return [True, min(left[1], node.data), max(right[2], node.data), left[3] + right[3] + 1] return [False, -1, -1, max(left[3], right[3])] return [True, math.inf, -math.inf, 0] return rec(root)[3] if someone needs python code -

[@Nintendo04]

finaly completed the entire series and got good concept of tree , thank you for quality content!

[@sujan_kumar_mitra]

Thanks for the series, it's really helpful. Waiting for your upcoming series.

[@YashveerGahlot-t6b]

thank u so much sir !!!! it will help me

[@ayushidalal5488]

Finally completed this series today! Learned a lot. Thanks :)

[@youracademicfriend-shashwa1051]

Thankyou Great Explanation!!

[@muditkhanna8164]

using the similiar approach here is the code for the maximum sum BST Leetcode 1373 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ int ans; //ans declared globally class bstnode{ public: bool valid; int maxl; int minr; int sumtotal; bstnode() { valid=true; maxl=INT_MIN; minr=INT_MAX; sumtotal=0; } }; class Solution { public: bstnode calc_sum(TreeNode*root) { if(root==NULL) { return bstnode(); } bstnode curr; bstnode left=calc_sum(root->left); bstnode right=calc_sum(root->right); //why max left and min right //well the highest max in left should be less than root->val and the lowest value in right should be less than root->val in order for it to be a bst //if the bst 's right and left are valid and maxleftvalvalval; //these next two steps are generally done for the recursion part //otherwise there's not much need after getting to know that it is a bst //as we are finding from bottom to root //the right min value will be compared with the right's left and right->val for min curr.minr=min(root->val,left.minr); //the left max value will be compared with the left's right and left->val for max curr.maxl=max(root->val,right.maxl); } else { //else make it false and the sum of that non bst will be either from right or left //because together left and right with node cannot be a bst so the right and root or left and root //will make bst, that's why taking the max of them curr.valid=false; curr.sumtotal=max(left.sumtotal,right.sumtotal); } //with every recursive call ans is updated we'll wait till the base condition and keep updating answer ans=max(ans,curr.sumtotal); //the return value is the valid bst for this recursive function return curr; } int maxSumBST(TreeNode*root) { ans=0; calc_sum(root); return ans; } };

[@akshaygill4692]

I have a doubt if inorder comes as sorted ,this proofs the tree is bst right ? Now the example striver have taken also gives inorder as sorted but it is not a bst why ? Please correct me if am wrong

[@aaravgulati1194]

See carefully the inorder traversal is not sorted

[@mmmm-wm8ci]

In right subtree with root 40 how minnode is 40 instead of 30.

[@parthsalat]

9:25 FIrst 19 will come then 16 will come

[@sauravchandra10]

So finally with efforts, I was able to complete this series. Commendable job striver

[@sandeep-sb]

Completed the Free ka Tree Series today. Thank you, Striver. I learned a lot from this series. Onto the next one :)

[@patilsoham]

did not understand: return NodeValue( min(root->val, left.minNode), max(root->val, right.maxNode), left.maxSize + right.maxSize + 1); can someone please explain?

[@tejassrivastava6971]

they are used to handle the NULL case when min is INT_MAX and max is INT_MIN.

[@amanbhadani8840]

This is condition of a valid BST, that is --- your current root's value is greater than the maximum of all nodes in left and current root's value is lesser than the minimum of all nodes in the right. Then this is considered a valid BST and we simply in min Node we return the minimum of (roots value and the minimum of all nodes in left) and in max Node we simply return the maximum of (roots value and maximum of all nodes in right) and since its a valid case ,in max size we return the sum of all nodes in the left of root +sum of all nodes in right of root+1(root itself) to get the count of total of nodes in a valid BST. Hope, I am able to clear your doubt.

[@fazilshafi8083]

Thank you! 🔥

[@jagjiwanchimkar8106]

When will you start Tries series!!

[@srinivasveligethi2380]

@11:27 I Guess minimal should be 30 instead of 40 becuase root should be less than or equal to minimal of right sub tree.

[@priyanshkumar17]

Yes

[@harshitparashar]

Another possible Brute: store inorder, check largest sorted array correct or not?

[@brainss5670]

I was thinking the same, also we need not to store the inorder too, we can just store previous node value in a variable and compare it with current node value, then it would be a O(n) time and O(1) space soln (not considering the recursion stack space) 🤔🤔

[@harshitparashar]

@@brainss5670 exactly That’s optimisation, basically peak n valley

[@tejassrivastava6971]

Tree: 4 2 5 1 0 inorder: 1 2 0 4 5 longest sorted array: 1 2 => size = 2 but its not a subtree since it has right node = 0 as well. Therefore approach is not correct.

[@brainss5670]

@@tejassrivastava6971 nice testcase man !

[@abhishekchoudhary5713]

@@tejassrivastava6971 Thanks for saving my time..:)

[@aryansinha1818]

Is it me only or it happened with others too, that this question took some time to be understood?

[@parthsalat]

It took me also more time than expected

[@aryansinha1818]

@@parthsalat Ok

[@shreyanshmittal9381]

happened with me as well, had to watch the video twice!

[@codding32world50]

Finally Compelted Yess it took me lot more time than expected... But it is with it.. Thank Youuu So much Striverrr

[@kO_SE__ShivamKumar]

A really nice explanation again!!!

[@ujjwalverma2870]

Finally Completed the Free the Tree series ,Thanks Bhaiya !!

[@SyedSameer-bk9pe]

How much time it can to complete this series

[@guptashashwat]

Commenting to mark, that I have completed this playlist. Thanks Striver!

[@souvickmazumdar8129]

Completed....A Big thanks to striver....Loved it