Dare2Solve
The numTrees
function computes the number of unique binary search trees (BSTs) that can be formed with n
distinct nodes, where each node contains values from 1 to n
. This problem is a classic example of dynamic programming and is related to the Catalan numbers.
The key observation is that the number of unique BSTs that can be formed with n
nodes is determined by considering each value as a possible root and calculating the number of possible left and right subtrees recursively. Specifically, for each possible root k
, the left subtree must contain nodes with values less than k
, and the right subtree must contain nodes with values greater than k
. The total number of BSTs is the sum of the products of the number of possible left and right subtrees for each possible root.
Dynamic Programming Array:
sol
of size n+1
to store the number of unique BSTs for each number of nodes from 0 to n
. Set sol[0]
and sol[1]
to 1, as there is exactly one BST that can be formed with 0 or 1 node.Filling the DP Array:
i
from 2 to n
.i
, iterate over possible root values j
from 1 to i
.j
, the number of unique BSTs with i
nodes is the sum of the products of the number of BSTs that can be formed with j-1
nodes on the left (stored in sol[j-1]
) and the number of BSTs that can be formed with i-j
nodes on the right (stored in sol[i-j]
).Final Result:
sol[n]
gives the number of unique BSTs that can be formed with n
nodes.The time complexity is (O(n^2)), where n
is the input number. This is because, for each number of nodes i
, we iterate through all possible root values j
, leading to a nested loop structure.
The space complexity is (O(n)), where n
is the size of the DP array sol
. This array stores the number of unique BSTs for each possible number of nodes from 0 to n
.
class Solution {
public:
int numTrees(int n) {
// Create 'sol' vector to store the solution...
std::vector<int> sol(n + 1, 0);
sol[0] = sol[1] = 1;
// Run a loop from 2 to n...
for (int i = 2; i <= n; i++) {
// Within the above loop, run a nested loop from 1 to i...
for (int j = 1; j <= i; j++) {
// Update the i-th position of the vector by adding the multiplication of the respective index...
sol[i] += sol[i - j] * sol[j - 1];
}
}
// Return the value of the nth index of the vector to get the solution...
return sol[n];
}
};
class Solution:
def numTrees(self, n: int) -> int:
# Create 'sol' list to store the solution...
sol = [0] * (n + 1)
sol[0], sol[1] = 1, 1
# Run a loop from 2 to n...
for i in range(2, n + 1):
# Within the above loop, run a nested loop from 1 to i...
for j in range(1, i + 1):
# Update the i-th position of the list by adding the multiplication of the respective index...
sol[i] += sol[i - j] * sol[j - 1]
# Return the value of the nth index of the list to get the solution...
return sol[n]
class Solution {
public int numTrees(int n) {
// Create 'sol' array to store the solution...
int[] sol = new int[n + 1];
sol[0] = sol[1] = 1;
// Run a loop from 2 to n...
for (int i = 2; i <= n; i++) {
// Within the above loop, run a nested loop from 1 to i...
for (int j = 1; j <= i; j++) {
// Update the i-th position of the array by adding the multiplication of the respective index...
sol[i] += sol[i - j] * sol[j - 1];
}
}
// Return the value of the nth index of the array to get the solution...
return sol[n];
}
}
var numTrees = function (n) {
// Create 'sol' array to store the solution...
var sol = [1, 1];
// Run a loop from 2 to n...
for (let i = 2; i <= n; i++) {
sol[i] = 0;
// Within the above loop, run a nested loop from 1 to i...
for (let j = 1; j <= i; j++) {
// Update the i-th position of the array by adding the multiplication of the respective index...
sol[i] += sol[i - j] * sol[j - 1];
}
}
// Return the value of the nth index of the array to get the solution...
return sol[n];
};