Description:
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.
Examples:
Example 1:
Input: n = 3
Output: 5
Example 2:
Input: n = 1
Output: 1Solution in Python:
To solve the problem of finding the number of structurally unique Binary Search Trees (BSTs) that can be formed with n nodes having unique values from 1 to n, we can use dynamic programming. This problem is related to the concept of Catalan numbers in combinatorial mathematics.
Python
class Solution:
def numTrees(self, n: int) -> int:
# dp array to store the number of unique BSTs for each number of nodes
dp = [0] * (n + 1)
# Base cases
dp[0] = 1 # An empty tree is a valid BST
dp[1] = 1 # A single node tree is a valid BST
# Fill the dp array using the recursive relation
for nodes in range(2, n + 1):
for root in range(1, nodes + 1):
left_trees = dp[root - 1] # number of unique BSTs formed by left subtree
right_trees = dp[nodes - root] # number of unique BSTs formed by right subtree
dp[nodes] += left_trees * right_trees
return dp[n]Explanation:
- Initialization:
dp = [0] * (n + 1)creates an array of sizen+1initialized to0.- Set
dp[0]anddp[1]to1since these are the base cases.
- Filling the DP array:
- For each number of nodes from
2ton, calculate the number of unique BSTs. - For each possible root from
1tonodes, compute the number of unique BSTs by multiplying the number of left subtrees (dp[root - 1]) and the number of right subtrees (dp[nodes - root]). - Sum up these products to get
dp[nodes].
- For each number of nodes from
- Return the result:
dp[n]will contain the number of unique BSTs that can be formed withnnodes.
This solution efficiently computes the number of unique BSTs using dynamic programming and ensures that each subproblem is solved only once.
Solution in Javascript:
JavaScript
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
// dp array to store the number of unique BSTs for each number of nodes
const dp = new Array(n + 1).fill(0);
// Base cases
dp[0] = 1; // An empty tree is a valid BST
dp[1] = 1; // A single node tree is a valid BST
// Fill the dp array using the recursive relation
for (let nodes = 2; nodes <= n; nodes++) {
for (let root = 1; root <= nodes; root++) {
const leftTrees = dp[root - 1]; // number of unique BSTs formed by left subtree
const rightTrees = dp[nodes - root]; // number of unique BSTs formed by right subtree
dp[nodes] += leftTrees * rightTrees;
}
}
return dp[n];
};Solution in Java:
Java
class Solution {
public int numTrees(int n) {
// dp array to store the number of unique BSTs for each number of nodes
int[] dp = new int[n + 1];
// Base cases
dp[0] = 1; // An empty tree is a valid BST
dp[1] = 1; // A single node tree is a valid BST
// Fill the dp array using the recursive relation
for (int nodes = 2; nodes <= n; nodes++) {
for (int root = 1; root <= nodes; root++) {
int leftTrees = dp[root - 1]; // number of unique BSTs formed by left subtree
int rightTrees = dp[nodes - root]; // number of unique BSTs formed by right subtree
dp[nodes] += leftTrees * rightTrees;
}
}
return dp[n];
}
}Solution in C#:
C#
public class Solution {
public int NumTrees(int n) {
// dp array to store the number of unique BSTs for each number of nodes
int[] dp = new int[n + 1];
// Base cases
dp[0] = 1; // An empty tree is a valid BST
dp[1] = 1; // A single node tree is a valid BST
// Fill the dp array using the recursive relation
for (int nodes = 2; nodes <= n; nodes++) {
for (int root = 1; root <= nodes; root++) {
int leftTrees = dp[root - 1]; // number of unique BSTs formed by left subtree
int rightTrees = dp[nodes - root]; // number of unique BSTs formed by right subtree
dp[nodes] += leftTrees * rightTrees;
}
}
return dp[n];
}
}