# 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; i def 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]; } }