LeetCode - Unique Binary Search Trees
source link: https://dev.to/_alkesh26/leetcode-unique-binary-search-trees-318c
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Problem statement
Given an integer n, return the number of structurally unique **BST's* (binary search trees) which has exactly n nodes of unique values from 1 to n*.
Problem statement taken from: https://leetcode.com/problems/unique-binary-search-trees.
Example 1:
Input: n = 3
Output: 5
Enter fullscreen mode
Exit fullscreen mode
Example 2:
Input: n = 1
Output: 1
Enter fullscreen mode
Exit fullscreen mode
Constraints:
- 1 <= n <= 19
Enter fullscreen mode
Exit fullscreen mode
Explanation
Brute force solution
The brute force approach is to generate all the possible BSTs and get the count. This approach will consume a lot of time when we increase n.
Dynamic Programming
With Dynamic Programming, we will reduce the scope of generating the BSTs and use mathematical concept to get the required result.
Let's take an example where n is 5. If node 2 is the root, then the left subtree will include 1 and the right subtree will include 3, 4, and 5. The possible number of combinations in the left subtree is 1, and in the right subtree is 5. We multiply 1 and 5. Similarly, if 3 is the root node, the possible number of combinations in the left subtree will be 2, and the number of combinations in the right subtree will be 2. So the total BST's when root node is 3 is 2*2 = 4. We add up all these combinations for each node 1 to n and return the required result.
A C++ snippet of the above approach is as below:
int numberOfBST(int n) {
int dp[n + 1];
fill_n(dp, n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] = dp[i] + (dp[i - j] * dp[j - 1]);
}
}
return dp[n];
}
Enter fullscreen mode
Exit fullscreen mode
The time complexity of the above approach is O(N^2) and space complexity is O(N).
Catalan numbers
[Catalan numbers (https://en.wikipedia.org/wiki/Catalan_number), in combinatorial mathematics, are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects.
It is denoted by Cn and the formula to calculate it is
(2n)! / ((n + 1)! * n!).
Let's check the algorithm to see how we can use this formula.
// numTrees function
- return catalan(2*n, n)
// catalan function
catalan(n , k)
- set result = 1
- if k > n - k
- k = n - k
- for i = 0; i < k; i++
- result *= (n - i)
- result /= (i + 1)
- return result/(k + 1)
Enter fullscreen mode
Exit fullscreen mode
The time complexity of this approach is O(N), and space complexity is O(1). Let's check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
long long catalan(int n, int k) {
long long result = 1;
if(k > n - k) {
k = n - k;
}
for(int i = 0; i < k; i++) {
result *= (n - i);
result /= (i + 1);
}
return result/(k + 1);
}
int numTrees(int n) {
long long result = catalan(2*n , n );
return (int) result ;
}
};
Enter fullscreen mode
Exit fullscreen mode
Golang solution
func catalan(n, k int) int {
result := 1
if k > n - k {
k = n - k
}
for i := 0; i < k; i++ {
result *= (n - i)
result /= (i + 1)
}
return result/(k + 1)
}
func numTrees(n int) int {
return catalan(2*n , n )
}
Enter fullscreen mode
Exit fullscreen mode
Javascript solution
var catalan = function(n, k) {
let result = 1;
if(k > n - k) {
k = n - k;
}
for(let i = 0; i < k; i++) {
result *= (n - i);
result /= (i + 1);
}
return result/(k + 1);
}
var numTrees = function(n) {
return catalan(2*n, n);
};
Enter fullscreen mode
Exit fullscreen mode
Let's dry-run our algorithm to see how the solution works.
Input n = 4
Step 1: result = catalan(2*n , n )
= catalan(2*4, 4)
= catalan(8, 4)
// catalan function
Step 2: result = 1
n = 8, k = 4
Step 3: if k > n - k
4 > 8 - 4
4 > 4
false
Step 4: loop for i = 0; i < k
0 < 4
true
result *= (n - i)
= result * (n - i)
= 1 * (8 - 0)
= 8
result /= (i + 1)
= result / (i + 1)
= 8 / (0 + 1)
= 8
i++
i = 1
Step 5: loop for i < k
1 < 4
true
result *= (n - i)
= result * (n - i)
= 8 * (8 - 1)
= 8 * 7
= 56
result /= (i + 1)
= result / (i + 1)
= 56 / (1 + 1)
= 56 / 2
= 28
i++
i = 2
Step 6: loop for i < k
2 < 4
true
result *= (n - i)
= result * (n - i)
= 28 * (8 - 2)
= 28 * 6
= 168
result /= (i + 1)
= result / (i + 1)
= 168 / (2 + 1)
= 168 / 3
= 56
i++
i = 3
Step 7: loop for i < k
3 < 4
true
result *= (n - i)
= result * (n - i)
= 56 * (8 - 3)
= 56 * 5
= 280
result /= (i + 1)
= result / (i + 1)
= 280 / (3 + 1)
= 280 / 4
= 70
i++
i = 4
Step 8: loop for i < k
4 < 4
false
Step 9: return result/(k + 1)
70/(4 + 1)
70/5
14
So we return the answer as 14.
Enter fullscreen mode
Exit fullscreen mode
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK