Largest BST in Binary Tree

[@ShaliniNegi24]

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

[@Sushil2874]

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

[@aneeinaec]

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

[@suryac850]

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

[@NurcanSonmezcr]

Thanks a lot Tushar! You have been really helpful!

[@chetak2]

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

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

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

[@dharanyuvi6951]

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

[@satya1067]

Awesome Explanation sir🤓🤓

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

[@chandralekha7717]

Thanks for making trees a simple concept

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

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

[@stith_pragya]

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

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

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

[@SilveraDavid]

Thanks you, very clear!!!

[@meghayall]

How about a video on B Tree?

[@jameslin9845]

The explanation is easy to understand. Thanks.

[@shiningyu9751]

Thank you for your crystal clear explanation! Very helpful!

[@vm1662]

Thanks a lot Tushar!

[@cmaheshster1]

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

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

[@SreyesSrinivasan]

Great explanation, thank you so much!

[@idontknow-wl6su]

Thanks for a clear explanetion :D

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

[@jinka99]

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

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

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

[@SBlogIndia]

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

[@mjdatt]

Thanks Tushar!! That was really helpful.

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

[@anuragdani9739]

A very good explanation...!

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

[@kartikchauhan5498]

Good guy Tushar

[@YogeshGuptaiamyogeshg]

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

[@YogeshGuptaiamyogeshg]

yes i realise, thanks.

[@pymondo1147]

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

[@lifehacks9450]

this is an amazing concept

[@parveshsingh6611]

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

[@varshapatidar7239]

very helpful ! Thanks..

[@swagatpatra2139]

good job Sir

[@HemanthKumar-od2ej]

superb explanation! :)

[@pennapatipavan5846]

Awesome bro. Thanks for such good explaination

[@namratakhandelwal8143]

very helpful !

[@spk9434]

Excellent !!

[@quantlfc]

Awesome.

[@rajeshd7389]

Nice Explanation !!

[@syedtahamohiuddin3160]

excellent !!!

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

[@stephyjacob1256]

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

[@arjoojain9809]

Awesome!

[@azharmarmu19]

Thanks a lot bro...

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

[@shivpratapsingh7992]

it was amzing! KEEP IT UP

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

[@sunilnk95]

good work :)

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

[@saifurrahmanbhuiyan925]

Brother we need Recursive Backtracking