Unique Binary Search Trees - Leetcode Solution

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]

1