Count unique BSTs.

We can assume a function for calculating the number of ways to calculate the number of trees for the given number of nodes for a fixed root. So we could calculate the number of ways to make a tree as follows. Let’s call the function F(‘X’) giving the number of trees given ‘X’ number of nodes.

We could calculate F(‘X’) = sum of { F(‘i’) * F(‘X’-1-’i’) }. Where i is the assumed number of nodes in the left child of the current root and so the number of remaining nodes for the right child is equal to (‘X’-1-i), hence we could add all these ways multiplicatively, so we could get the total number of ways. 

This value of this function is also defined as Catalan number, which has a specified formula which is equal to ((2*NUM) C (NUM) / (NUM+1)) , but we will calculate the value recursively.

Steps for calculating assuming ‘NUM’ number of nodes in the given tree are as follows: 

1. If ‘NUM’ is equal to 0 or 1, return the answer as 1, as there is only one tree.
2. Declare variable ‘SUM’ and initialize it with 0, where sum will store the count of total structurally unique binary search trees.
3. Run a loop for ‘i’ = ‘0’ to ‘NUM’-1:
   1. ‘SUM’ = ‘SUM’ +  F(‘i’) * F(‘NUM’-1-’i’) to the answer.
4. Finally, return ‘SUM’ as the answer.

As discussed in Approach-1, we will calculate the number of ways of forming Unique BSTs using recursion. But what changes here is that instead of calculating recursively the already calculated results, we will use a vector/list ‘MEMO’ to store the value of that number (where ‘MEMO’ will store the value for each index as a number) and pass along with the function recursively. 

When calculating for a number in a function, we will check if the value for that number is already calculated. Then we will simply return that value and avoid the overhead of recursion. If the value is not already calculated then we will do the same recursion process of the function call.

Steps involved in this approach: 

• We will declare and initialize the vector/list ‘MEMO’ of size ‘NUM’+1 with -1 for each index, where ‘MEMO’ will store the value for each index as a number.
• Pass ‘MEMO’ along with ‘NUM’ in the recursive function.

We need to just make changes in the recursive function:

• If ‘MEMO[‘NUM’]’ is not equal to -1, it means its value is already calculated. So,
  • Return ‘MEMO[‘NUM’]’.

The rest algorithm is the same as Approach-1.

We can notice that, as we are memoizing the return values in Approach-1, we can avoid overlapping subproblems, and our runtime complexity could be significantly better. We could make our runtime complexity from exponential to polynomial. Here we will discuss the tabulation method.

Here we will iterate from 0 to ‘NUM’ and for each number in the iteration we will model the answer till that index with the same method as recursion as discussed in Approach-1. Thus, in this way, we will build our answer with each index and form our answer for ‘NUM’ in ‘ways[‘NUM’]’ where ‘ways’ is the array/list to store the answers for each number index in the iteration. 

The steps are as follows: 

1. Declare a list/array of ‘NUM’+1 size, named as ‘WAYS’, so we could count the number of ways assuming each number from ‘0’ to ‘NUM’ as the number of nodes in the tree and store it in ‘WAYS[i]’.
2. Assign 1 to both ‘WAYS[0]’ and ‘WAYS[1]’, as there is only one way for each node to make a tree.
3. Run a loop for ‘i’ from 2 to ‘NUM’:
   • Run a loop fo ‘j’ from 0 to less than ‘i’:
     1. ‘WAYS[i]’ += ‘WAYS[j]’ * ‘WAYS[i - j - 1]’.
4. Finally, return ‘Ways[‘NUM’].