Unique Binary Search Trees - Leetcode 96 - Python Dynamic Programming

0:00 - Conceptual
6:25 - Coding solution

#amazon #interview #question

Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[TrollFreeInternet]

I think there is a mistake with the last value at 7:45...it should be numTree[3]* numTree[0]..not numTree[3]*numTree[1]... it won't make difference to the answer but it might confuse some people.

[lizziedaffofil]

No one can beat you in giving such a clear explanation even to complex topics! Way to go!

[JuHan]

Thanks for posting it! Java version in case anyone's interested

class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int nodeCount = 2; nodeCount <= n; nodeCount++) {
int total = 0;
for (int root = 1; root <= nodeCount; root++) {
int left = root - 1;
int right = nodeCount - root;
total += dp[left] * dp[right];
}
dp[nodeCount] = total;
}
return dp[n];
}
}

[uncleroku]

Question: at 7:40 you said that when you get to the last value (the node being 4). You'd have one node in your right subtree. Wouldn't it be zero values in your subtree when 4 is the root, since all other nodes would be smaller?

[aatishjain]

Had no idea how to approach this problem after reading the problem statement. Not sure when will get over this. As always best and savior for us. Thanks a ton bro.

[AlfranAli]

For this particular problem, if you see the pattern it's following catalan number which can be solved in O(n) time & O(1) space, just mentioning it here for future readers to go and check that out too. Nice initiative, keep up the good work! :)

[jonaskhanwald]

Nice intuition, below is the recursive solution

def numTrees(self, n: int) -> int:
@cache
def f(n):
if n == 0:return 1
res = 0
for i in range(0, n): res += (f(i) * f(n-i-1) )
return res
return f(n)

[mayankkhanna]

If I got this problem in an interview, I would cry. But not anymore..

[mehulsolanki]

My recursive solution with memoization:

def numTrees(self, n: int) -> int:

self.trees = {}
self.trees[0] = 1
self.trees[1] = 1
self.trees[2] = 2

return self.getTrees(n)

def getTrees(self, n):

if n in self.trees:
return self.trees[n]

l, r = 0, n-1

res = 0
while r>=0:
res += ( self.getTrees(l) * self.getTrees(r) )
l += 1
r -= 1

self.trees[n] = res
return res

[arsahilar]

@7:44 fOR LAST VALUE shouldn't it be NODE[3] in left * and NODE[0] on right

[chujunlu]

When you change variable i, j from Leetcode's solution to something descriptive, like this video does, suddenly the underlying thinking comes through, and the code makes sense.

[tripathi]

was struglling for one day and then i found this helpful video, very well done

[polyrain]

Why did you n+1 in the memo table? Just to capture numTree[0]? Great vid!

[nikhilgoyal]

thanks! for line #13 - I would have think - root should go from 0 to node +1 ( even if left is None for root = 0 - there our some combinations that will result from the right side ?). what am i missing pls ?

[apoorvbedmutha]

The explainnation is so good ! you're an absolute legend

[atanunayak]

I understand everything in the solution, except for the thing that why do we just multiply the values, I mean there can be other cases as well right?
Let me elaborate,
If you draw the diagram for 5 nodes solution, for f(5) we have f(3)*f(1) is good, but the three on the left also have 4C3 choices right?

[safagoktanbayraktar]

The moment I've seen this question, immediately I've thought about recursive approach, just like Fibonacci can be solved with loops and recursion. For those who wants to understand the recursive approach, I am leaving c# solution, it's pretty straight forward, does exactly the same thing in the same order - a bit cleaner.

public class Solution {
private Dictionary<int, int> memo = new Dictionary<int, int>();

public int NumTrees(int n) {
if (n <= 1)
return 1;

if (memo.ContainsKey(n))
return memo[n];

int total = 0;
for (int root = 1; root <= n; root++) {
total += NumTrees(root - 1) * NumTrees(n - root);
}
memo[n] = total;
return total;
}
}

[pahehepaa]

Thanks! This was sweet. Easy to understand. Other videos are complicating stuff 😶 Subscribed.

[shuvbhowmickbestin]

Do you type with your mouse? I hear the clicking sounds.

[siningsun]

The best explanation I've ever seen.