Unique Binary Search Trees | Count all structurally unique BSTs | Catalan number | Leetcode #96

This video explains a very important programming interview problem which is to count the number of structurally unique binary search trees (BSTs) having N nodes.I have shown the idea of conversion of this problem from given state to finding the Nth catalan number.This problem can be solved by recursion, dynamic programming and also simply by using the binomial formula for finding Nth catalan number.I have taken sufficient examples to show the intuition and approach and at the end of the video, i have also shown the code walk-through. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
CATALAN NUMBER: • How to calculate Catal...

[@prestoX]

Most intuitive, thanks a ton buddy, I was reading Leetcode blogs for 3 days with all crappy methods, yours is simply brilliant and clear !

[@bhuwansingh2534]

The only time JEE level maths was used again.

[@shresthmishra9329]

This explanation helped me to solve another famous problem ''intersecting chords in a cirlce". Thank you tech dose.

[@techdose4u]

Welcome :)

[@vipulsharma7190]

how did you solve that by using this?

[@shresthmishra9329]

@@vipulsharma7190 Because it can be solved using catalan number method.
Suppose you a have a circle wihtout any cuts then it is complete 1 unit.
But when you make 1 cut then circle is distributed in two parts. (1+1=2). Then when you make the second cut total number of parts of the circle will be 2 parts pahle se the + 2 (because this is the second cut) . Now in total you have 4 cuts. And now if you cut the third cut then 4 pahle se + 3(because this is the third cut). So total parts of circle is 7. Again if make the 4th cut then 7 + 4 (4 becauae this is the 4th cut) So total parts of circle = 11.
And this is how it goes on which can be solved with the help of catalan number method.

[@vipulsharma7190]

@@shresthmishra9329 thanks bro for explanation

[@shresthmishra9329]

@@vipulsharma7190 ☺️

[@sujithns5033]

This channel is very underrated. Nice explanation!

[@techdose4u]

Thanks

[@ravipatiramya4185]

@@techdose4u can u share the link where u exaplained Catalan number

[@anitasrivastava983]

The man , the myth , the legend uploads once again!

[@techdose4u]

😅

[@uditghosh3247]

Coldzera!!!!

[@kunalsoni7681]

Such a great video explanation ☺️😊.. thank you sir

[@techdose4u]

Welcome

[@kuangyimeng8850]

very clear explanation. Thank you.

[@melwinalm]

As always, great explanation

[@techdose4u]

Thanks

[@bhavitmathur5476]

Very Helpful Videos. Please keep posting

[@nagalakshmi1385]

very good video, first time subscriber, want to check out your other videos too. your implementation is Order of n square. Order of n implementation is " long Cn=1;
for(int n=0;n

[@BarkaDog]

In interviews, you can be expected to explain more than one approach. So you should always be prepared.

[@techdose4u]

Yes true

[@aadityakiran_s]

Hey, your channel is great and your explanations are very nice. I also noticed that your handwriting is very legible. What's the setup you use for whiteboarding? Do you do it using a digital drawing pad?

[@Utkarshkharb]

Very well explained. Subbed!

[@techdose4u]

Thanks 😊

[@biranchinarayanpadhi9067]

Brillaint 3xplanation bro!!!

[@techdose4u]

Thanks

[@chetanpatteparapu7600]

This is very helpful bro ... Thanks a lot..

[@techdose4u]

Welcome :)

[@yitingg7942]

Thank you by watching this video alone I know how to solve it. What about 95. Unique Binary Search Trees II ? I think it's much harder than this.

[@techdose4u]

Yea it must be!! Since you told me 😅 lol

[@deepakjoshi4374]

5:21, one small correction, the correct formula will be Cn=∑i=0,n−1 (CiCn−i−1. ) It will go to n-1, not upto n.

[@okeyD90232]

You should add this to your tree playlist.

[@techdose4u]

Sure

[@siddhartha.saif25]

very helpful. thanks

[@techdose4u]

Welcome

[@meghamalviya8495]

Can you please clear my doubt as to why and how we would have only 3 combinations of 2,3,4 (i.e. c3) in the right subtree when taking 1 as a root? Why won't there be 5 structurally unique combinations at there (for 2,3,4) because we would get 5 as a answer when we have n=3?

[@techdose4u]

Actually C3 means count of no of unique BSTs with 3 unique numbers. It is not an exact value. Think of it as an unknown constant.

[@meghamalviya8495]

@@techdose4u ohk..thanks!

[@paragroy5359]

Nice explanation sir...

[@techdose4u]

Thanks :)

[@rimpiranibaruah5353]

Great explanation

[@techdose4u]

Thanks :)

[@kunalsoni7681]

Helpful video 😊 too much for interview
Thank you always

[@techdose4u]

Welcome

[@devanshgoel3433]

thank u sir!

[@ayushganguli1359]

Hi, could you please upload a video to generate unique binary search tree in the range [1,n] please

[@techdose4u]

Sure. That is an extended question.

[@lokeshojha1542]

int count_BT(int n){
if(n

[@orugantilokesh1579]

I am viewing the solution directly , i couldn't think of any method to solve it , is it alright or should i change my approch.

[@BarkaDog]

If you made no progress in 30 minutes then look at the solution.

[@techdose4u]

It's alright. You don't have to know everything. Just keep learning new concepts.

[@SiddheshKukade]

thanks

[@kevinchittilapilly8221]

Can anyone explain why T[0] is taken as 1? If there are no nodes then shouldn't total bst be 0?

[@calvin2042]

No structure is a unique structure.

[@SuhasSrivats]

In short, this is the formula:
Catalan Number = (2n)!/((n+1)!*n!)

[@techdose4u]

Right

[@abhijeetkumar2204]

class Solution {
long long dp[100000]={0};
int catalan(int n)
{
if(n==0)
{
return 1;
}
if(dp[n]!=0)
{
return dp[n];
}
int ans=0;
for(int i=1;i

[@techdose4u]

👍

[@aayush5474]

Itna mazaa kyu aa rha haiii😀

[@techdose4u]

😂

[@pwnweb5734]

AND.. how are we supposed to come up with this formula during interview ? NOP , not intuitive

[@AmanSharma-or5vh]

best

[@thoufeequeshaque3937]

first example binary search tree (BST) structure is invalid .
All nodes in the right subtree of a node must have values greater than the node's value.
All nodes in the left subtree of a node must have values lesser than the node's value.

[@rajaganji7982]

when n=4;
C0=0;
C1=1;
C2=2;
C3=3;
= C0*C1 + C1*C2 + C2*C1 + C3*C
= 0*3 + 1*2 + 2*1 + 3*0
= 4.
But 4 is wrong. Please let me know if I am wrong.

[@Official-tk3nc]

Great video . I think you are an Indian because no one in youtube could teach better than Indian ...... atleast cse concepts :) ###nitjstudenthere

[@alirezaamedeo]

5:22 You wrote Catalan number wrong. It should be C(n+1) = Sigma...

[@ashutosh61290]

jab sb kuch dusre video se hi dekhna tha toh ye video kyu bnaye ??