Largest BST in Binary Tree

[@aneeinaec]

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

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

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

[@sasirekhamsvl9504]

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

[@03Karthikeyan]

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

[@alexcomas2934]

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

[@dharanyuvi6951]

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

[@chandralekha7717]

Thanks for making trees a simple concept

[@ErfanHossainShoaib]

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

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

[@stith_pragya]

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

[@idontknow-wl6su]

Thanks for a clear explanetion :D

[@SilveraDavid]

Thanks you, very clear!!!

[@jameslin9845]

The explanation is easy to understand. Thanks.

[@jinka99]

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

[@SreyesSrinivasan]

Great explanation, thank you so much!

[@shiningyu9751]

Thank you for your crystal clear explanation! Very helpful!

[@meghayall]

How about a video on B Tree?

[@kumarsrijan7566]

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

[@mjdatt]

Thanks Tushar!! That was really helpful.

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

[@MohitG7701]

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

[@vm1662]

Thanks a lot Tushar!

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

[@SBlogIndia]

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

[@anuragdani9739]

A very good explanation...!

[@rajeshd7389]

Nice Explanation !!

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

[@pennapatipavan5846]

Awesome bro. Thanks for such good explaination

[@HemanthKumar-od2ej]

superb explanation! :)

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

[@spk9434]

Excellent !!

[@kartikchauhan5498]

Good guy Tushar

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

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

[@namratakhandelwal8143]

very helpful !

[@pymondo1147]

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

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

[@varshapatidar7239]

very helpful ! Thanks..

[@lifehacks9450]

this is an amazing concept

[@shivpratapsingh7992]

it was amzing! KEEP IT UP

[@swagatpatra2139]

good job Sir

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

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

[@syedtahamohiuddin3160]

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

[@cmaheshster1]

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

[@stephyjacob1256]

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

[@parveshsingh6611]

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

[@quantlfc]

Awesome.

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

[@arjoojain9809]

Awesome!

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

[@YogeshGuptaiamyogeshg]

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

[@YogeshGuptaiamyogeshg]

yes i realise, thanks.

[@azharmarmu19]

Thanks a lot bro...

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

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

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