Largest BST in Binary Tree

[@ShaliniNegi24]

I cannot frame the sentence to tell you how much I respect you! God bless you!

[@aneeinaec]

This guy has ZERO drama... To the point allways..❤️

[@Sushil2874]

Tremendous explanation..!! I mean this guy makes everything so easy and simple..!! Thanks a lot Tushar..!!

[@suryac850]

Thanks. Got this in an interview, but was stuck in trying to solve the problem. This video helped me understand the concept easily.

[@chetak2]

Great!! I must have watched about 25 of your videos on different CS topics! Love it

[@NurcanSonmezcr]

Thanks a lot Tushar! You have been really helpful!

[@alexcomas2934]

Awesome video, just tried this on leetcode and your explanation helped me understand the problem more.

[@03Karthikeyan]

Thank you Tushar! I have been following your videos for over a year and have been spreading the word. Keep them coming.

[@sasirekhamsvl9504]

Tu si great ho Tushar. No one can explain this better!!!!!!!!

[@ErfanHossainShoaib]

Your all videos are simply excellent, awesome and too much helpful. Thanks

[@dharanyuvi6951]

Thanks alot Tushar and your code also very clean and self explanatory

[@chandralekha7717]

Thanks for making trees a simple concept

[@jinka99]

Thank you Tushar ! This has been very helpful ! thanks for making these videos

[@shiningyu9751]

Thank you for your crystal clear explanation! Very helpful!

[@satya1067]

Awesome Explanation sir🤓🤓

[@stith_pragya]

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

[@ajaygaur3392]

That elegant code, though. Thanks.

[@leroyjamison5700]

i know Im asking randomly but does anyone know a tool to log back into an instagram account? I was stupid lost my login password. I would love any help you can give me.

[@kartermarcus3565]

@Leroy Jamison instablaster :)

[@leroyjamison5700]

@Karter Marcus I really appreciate your reply. I found the site through google and im trying it out atm. Looks like it's gonna take a while so I will get back to you later when my account password hopefully is recovered.

[@leroyjamison5700]

@Karter Marcus it did the trick and I finally got access to my account again. I'm so happy:D Thank you so much, you saved my ass !

[@kartermarcus3565]

@Leroy Jamison No problem xD

[@jameslin9845]

The explanation is easy to understand. Thanks.

[@harshitajain323]

your all videos are excellent am learning tree concepts from all your videos...just a request it well be great if you post lecture on binomial tree

[@SilveraDavid]

Thanks you, very clear!!!

[@SreyesSrinivasan]

Great explanation, thank you so much!

[@omkarsharan3967]

as you told BST definition in starting of this video, 25 is the root of the tree and a leaf node also have a value 25 so I think its answer should not be 8.

[@idontknow-wl6su]

Thanks for a clear explanetion :D

[@mjdatt]

Thanks Tushar!! That was really helpful.

[@kumarsrijan7566]

Tell you what this channel was ahead of it's time

[@zhaodelong]

when child node is null, the min / max of the parent should be parent.val, not 0. if it's 0, it will fail the Leetcode OJ

[@MohitG7701]

awesome explanation sir...this video of yours is truly helpful....thanks a lot sir for making this video

[@hanusrikannan]

Excellent explanation. I went through your code in github for this problem. When either left subtree is not BST or right sub tree is not BST, shouldnt we have to set the size of BST as the size of subtree which is BST. If both sub tree's are not BST, then set the size of current sub tree as zero

[@pymondo1147]

1 lakh subcriptions ..You deserve iit sir :):) Thank you for your efforts:)

[@SBlogIndia]

The explanation is good, but most I liked the git hub code

[@meghayall]

How about a video on B Tree?

[@1gouravgg]

thanks for your efforts Tushar. would you mind making some videos for backtracking programs.In spite of their utter importance in interview round there aren't any good tutorials available on net.

[@pennapatipavan5846]

Awesome bro. Thanks for such good explaination

[@anuragdani9739]

A very good explanation...!

[@vm1662]

Thanks a lot Tushar!

[@HemanthKumar-od2ej]

superb explanation! :)

[@kartikchauhan5498]

Good guy Tushar

[@rajeshd7389]

Nice Explanation !!

[@lifehacks9450]

this is an amazing concept

[@shivpratapsingh7992]

it was amzing! KEEP IT UP

[@s1337m]

Can you explain why the first approach is O(n^2)?

[@nikkinic112]

I can give a brief explanation. If you check each node individually if they are BST, you are repeating a lot of steps right? if you check the node and the whole tree if it is BST, you have to check if the left node is also a BST, and so forth. But when you check that the root is not a BST, then you have to check if the left node is also a BST again. So for each N node, you are doing as least 1....N more BST checking.

[@bismitabhattacharjee4686]

I would think node 19 returns (F,2,0,0) to node 18, not (F,1,0,0), correct me if I am wrong

[@cmaheshster1]

The BST can include only left or right and become a binary tree right?

[@ditibagga9255]

If we find inorder at each root, and see which is the longest sorted one, won't that solve the problem?

[@shivansh-gup]

no because BST must include leaf nodes and longest sorted one in inorder array does not guarantee this

[@namratakhandelwal8143]

very helpful !

[@adis6867]

Doing inorder traversal and finding the longest increasing subarray will work??

[@vl5397]

In this example, the longest increasing subarray in the inorder traversal is [20 25 35 40 50 55 60 70]. Size of the subarray is 8. So, yes, your suggestion seems to work. The post-order traversal in the video will also be able to give you the head of the BST. In the above array, the head node is not apparent. Edit: Perhaps, it can.

[@adis6867]

@@vl5397 i think it can be done even without using space, i mean do inorder traversal and keep track of previous visited node and keep comparing. If present node is greater than prev node increment counter else make it zero and keep track of max value of counter. Although i have not implemented but will try tomorrow.

[@vl5397]

@@adis6867 Yes, I think you have outlined the procedure well. On leetcode, this problem is premium, unable to try it out.

[@adis6867]

@@vl5397 i too tried but faced same issue, if you are able to find it on GitHub or other solution then please share, bcz this solution is good but i would not have solved it naturally of my own.

[@varshapatidar7239]

very helpful ! Thanks..

[@1388tushr]

Hi Tushar, the explanation was simple and easy to understand. I think instead of using postorder traversal, easier way out is to do an inorder traversal on the tree and store the output of inorder node values in an array. Once this is done just find out the maximum increasing subsequence in the array. This will give you the size of the largest BST in a binary tree.

[@shankardaruga3264]

Yes. That should be the correct sub Tree. Here We are not considering all the possible sub Trees. Here we are only checking sub trees that traverse up till the leaf and also, the left and right should be sub trees to be considered.

[@kartikchauhan5498]

No, your solution won't work for all the cases. Take this case for example- 5 / \ 4 6 / \ 25 2 ur logic's ans : size 3 (4 5 6) original ans : size 1

[@xxbighotshotxx]

@@kartikchauhan5498 You're correct. Thanks for the counterexample

[@swagatpatra2139]

good job Sir

[@spk9434]

Excellent !!

[@koustavchatterjee2907]

Hey Tushar, can you publish some videos on suffix array creation algorithm ?

[@koustavchatterjee2907]

Thanks buddy

[@koustavchatterjee2907]

***** tushar, it will be great if it is a O(n) algo

[@dronelektron]

Koustav Chatterjee and suffix tree (Ukkonen) :3

[@dronelektron]

Waiting :3

[@subashsah4831]

Its a request plz also upload the code for all your videos in c or c++

[@harsha-ix9le]

Hi tushar, .. .50 .../ ........ \ ..30........ 60 ../.....\...... /.. \ .5.... 20.... 55...70 ..................... /.....\ .....................65 80 Cant we perform inorder traversal.and keep count like for suppose intialize max count=0; count=1; 1.5

[@harsha-ix9le]

+Tushar Roy 10 / 1 is a BST only right?

[@parveshsingh6611]

@Tushar roy Logic is fine but you should also explain the code.

[@stephyjacob1256]

Thanks Gautam gambhir. Oh sh*t. ..I mean Tushar . :p

[@syedtahamohiuddin3160]

excellent !!!

[@azharmarmu19]

Thanks a lot bro...

[@quantlfc]

Awesome.

[@YogeshGuptaiamyogeshg]

What if we traverse inorder and find maximum patch of elements which are in sorted order..

[@YogeshGuptaiamyogeshg]

yes i realise, thanks.

[@arjoojain9809]

Awesome!

[@sunilnk95]

good work :)

[@ayushmantiwari7547]

//Suggest improvement if any..BTW giving correct output...in C++ //largest BST from BT #include using namespace std; struct Node { int data; Node *left; Node *right; Node(int val) { data = val; left = NULL; right = NULL; } }; struct Data { int mini; int maxi; int size; bool isbst; }; Data largestBSTinBT(Node *root) { if (root == NULL) { return {INT_MAX, INT_MIN, 0, true}; } if (root->left == NULL && root->right == NULL) { return {root->data, root->data, 1, true}; } Data Left = largestBSTinBT(root->left); Data Right = largestBSTinBT(root->right); Data curr; if (root->data < Right.mini && root->data > Left.maxi && Left.isbst && Right.isbst) { curr.size = Left.size + Right.size + 1; if(Left.mini!=INT_MAX) curr.mini = Left.mini; else curr.mini=root->data; if(Right.maxi!=INT_MIN) curr.maxi = Right.maxi; else curr.maxi=root->data; curr.isbst = true; return curr; } else { curr.size = max(Left.size, Right.size); curr.mini = 0; curr.maxi = 0; curr.isbst = false; return curr; } } int main() { Node *root = NULL; root = new Node(25); root->left = new Node(18); root->right = new Node(50); root->left->left = new Node(19); root->left->right = new Node(20); root->left->left->right = new Node(15); root->left->right->left = new Node(18); root->left->right->right = new Node(25); root->right->left = new Node(35); root->right->right = new Node(60); root->right->right->left = new Node(55); root->right->right->right = new Node(70); root->right->left->right = new Node(40); root->right->left->left = new Node(20); root->right->left->left->right = new Node(25); Data S = largestBSTinBT(root); cout

[@sinboowang8063]

coooooooooool

[@saifurrahmanbhuiyan925]

Brother we need Recursive Backtracking

[@madhukiranattivilli2321]

But there are 2 ways to determine largest bst in a bt (1) what tushar did -- if the subtree with node X as root is a BST, but is not a BST when associated with X's parent, DISASSOCIATE WITH PARENT and the subtree with X as root is one of the contenders for LARGEST BST. Here Tushar used POSTORDER TRAVERSAL (2) another way -- if the subtree with node X as leaf is a BST, but is not a BST when associated with X's child, DISASSOCIATE WITH CHILD AND MAKE X AS A BST LEAF. Here we can use the algo "Is BT a BST", wherein if (a, b) are (minval, maxval) for node X, (a, X) and (X, b) would be the (minval, maxval) for X's left and right children respectively. Wherever this assertion fails, that child of X would be made NULL, thus disassociating from the BT to maintain it as a BST. :) Please comment

[@KUSHUTRIVEDI]

Hello Sir, I have question - If we do not include 19 and 15 in left subtree of 25 and 20 and 25 on right subtree, that would still be a BST. Size would be 11. Why did not count 18(root -> left) and 25(root), in our largest BST? Thank you in advance.

[@KUSHUTRIVEDI]

***** Thank you sir..!