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 :)

=================================================================
=================================================================

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

[anitasrivastava]

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

[shresthmishra]

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

[sujithns]

This channel is very underrated. Nice explanation!

[bhuwansingh]

The only time JEE level maths was used again.

[nagalakshmi]

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<num;n++)
Cn = Cn * 2 *(2*n+1)/(n+2);

return (int)Cn;"

[deepakjoshi]

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.

[bhavitmathur]

Very Helpful Videos. Please keep posting

[kunalsoni]

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

[Official-tknc]

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

[chetanpatteparapu]

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

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

[yitingg]

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.

[okeyD]

You should add this to your tree playlist.

[kunalsoni]

Helpful video 😊 too much for interview
Thank you always

[rajaganji]

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.

[abhijeetkumar]

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

int ans=0;
for(int i=1;i<=n;i++)
{

}
//if we are computing for first time
dp[n]=ans;

return ans;
}

public:
int numTrees(int n) {
return catalan(n);
}
};

[orugantilokesh]

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.

[meghamalviya]

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?

[thoufeequeshaque]

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.