Solution For Unique Binary Search Trees
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.
Solution approach:
The problem can be solved using dynamic programming approach. The idea is to count the number of unique binary search trees that can be formed with n nodes.
To count the number of unique binary search trees, we can use the fact that each number from 1 to n can be the root of the BST. When i is the root of the BST, the left subtree will have i-1 nodes and the right subtree will have n-i nodes. We can use this fact to recursively count the number of unique BSTs that can be formed with i-1 nodes in the left subtree and n-i nodes in the right subtree.
To avoid calculating the same values multiple times, we can store the values in a memoization array and use them when needed.
Algorithm:
1. Create a memoization array of size n+1 and initialize it with 0.
2. memo[0] and memo[1] are initialized with 1 since there is only one way to form a BST with 0 or 1 nodes.
3. For i from 2 to n+1, do the following:
a. For j from 1 to i, do the following:
i. memo[i] += memo[j-1]*memo[i-j]
4. Return memo[n].
Explanation:
1. Create a memoization array of size n+1 and initialize it with 0 to avoid calculating the same values multiple times.
2. memo[0] and memo[1] are initialized with 1 since there is only one way to form a BST with 0 or 1 nodes.
3. We loop from 2 to n+1 since we know that there must be at least 2 nodes to form a BST. We loop through j from 1 to i since j can be the root of the BST. For each j, we calculate the number of unique BSTs that can be formed with j-1 nodes in the left subtree and i-j nodes in the right subtree. We multiply these values and add it to memo[i] since we are counting the number of unique BSTs that can be formed with i nodes. At the end of the loop, memo[i] will contain the number of unique BSTs that can be formed with i nodes.
4. We return memo[n] since we are interested in the number of unique BSTs that can be formed with n nodes.
Time complexity: O(n^2)
Space complexity: O(n)
Solution code in Python:
class Solution:
def numTrees(self, n: int) -> int:
memo = [0](n+1)
memo[0],memo[1] = 1,1
for i in range(2,n+1):
for j in range(1,i+1):
memo[i] += memo[j-1]memo[i-j]
return memo[n]
Step by Step Implementation For Unique Binary Search Trees
There are several solutions to this problem, but one Java solution is to use recursion. First, we need to define a helper function that takes in an integer n and returns the number of unique binary search trees that can be created with n nodes. We can then use this helper function in our main function to calculate the number of unique binary search trees that can be created with a given number of nodes.
Helper Function:
int helper(int n) {
// Base case: if n is 0 or 1, then there is only 1 unique binary search tree that can be created
if (n <= 1) {
return 1;
}
// Recursive case:
// Use the formula: T(n) = T(0)*T(n-1) + T(1)*T(n-2) + ... + T(n-1)*T(0)
// Where T(n) is the number of unique binary search trees that can be created with n nodes
// T(0) is the number of unique binary search trees that can be created with 0 nodes (which is 1)
// T(1) is the number of unique binary search trees that can be created with 1 node (which is 1)
int sum = 0;
for (int i=0; idef numTrees(n):
# Base case
if n == 0 or n == 1:
return 1
# Store the result in a list so that we can
# return the value from the last call
dp = [0]*(n+1)
# Base case
dp[0] = 1
dp[1] = 1
# Fill the entries in dp using recursive
# formula explained above
for i in range(2, n+1):
for j in range(1, i+1):
dp[i] = dp[i] + dp[j-1]*dp[i-j]
return dp[n]There are many solutions to this problem, but one possible solution is as follows:
//Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
//For example,
//Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
//Solution 1: Recursive Solution
var numTrees = function(n) {
//Base case:
if(n <= 0) {
return 0;
}
//Recursive case:
if(n === 1) {
return 1;
}
let count = 0;
for(let i = 1; i <= n; i++) {
let left = numTrees(i - 1);
let right = numTrees(n - i);
count += left * right;
}
return count;
};There are many possible solutions to this problem. One solution is to use a recursive approach, as follows:
int numTrees(int n) {
// Base case: if n is 0 or 1, there is only 1 possible tree
if (n <= 1) return 1;
// Now consider the case where n is greater than 1.
// We need to calculate the number of possible trees
// with values 1, 2, ..., n.
// The number of possible trees with value i
// as the root node is equal to the number of
// possible trees with values 1, 2, ..., (i-1)
// as the root nodes, multiplied by the number
// of possible trees with values (i+1), (i+2), ..., n
// as the root nodes.
// Thus, the total number of possible trees is:
int total = 0;
for (int i = 1; i <= n; i++) {
int left = numTrees(i - 1);
int right = numTrees(n - i);
total += left * right;
}
return total;
}public class Solution {
public int NumTrees(int n) {
//dp[i] represents the number of unique BSTs that can be formed with i nodes
int[] dp = new int[n+1];
//base case: with 0 nodes there is 1 unique BST that can be formed (the empty tree)
dp[0] = 1;
//base case: with 1 node there is 1 unique BST that can be formed (the tree with a single node)
dp[1] = 1;
//for each node i from 2 to n:
for(int i = 2; i <= n; i++){
//for each node j that can be the root of a tree with i nodes:
for(int j = 1; j <= i; j++){
//the number of unique BSTs that can be formed with i nodes is the sum of:
//1. the number of unique BSTs that can be formed with j-1 nodes if j is the root
//2. the number of unique BSTs that can be formed with i-j nodes if j is not the root
dp[i] += dp[j-1] * dp[i-j];
}
}
//return the number of unique BSTs that can be formed with n nodes
return dp[n];
}
}