Total number of possible Binary Search Trees with n nodes-Part2

Explaining the Algorithm

Here we are not interested in the content of the nodes,but just the number of nodes.when we are considering the ^jth element as the root, we know that 1 to j-1 are in the left of j in the  tree and j+1 to N are on the right of j in the  tree.Let's start with the same N nodes, those we discussed in our previous series.

NosOfBST(with N nodes) = NosOfBST(Node 1 as root) + NosOfBST(Node 2 as root) + … +NosOfBST (Node k as root) + … + NosOfBST(Node N as root).

We can write the same mathematically as

                                         N
NosOfBST(with N nodes)=  ∑  NosOfBST(Node i as root)
                                        i=1 


But as we know the nos of BST at a node i as root is the multiplication of the nos of BST in its left subtree and nos of BST in its right subtree.

so the same can be written as


                                             N
NosOfBST(with N nodes)=      ∑  NosOfBST(k-1)*NosOfBST(N-k)
                                           k=1

When we know that for a given root  if there are 3 elements in the left, then we know there are five possibilities in the left as in Answer 4. If we have two elements in the right of RT, then we know there are 2 possibilities in the right as in answer 3. Then we multiply both of them i.e. 5 * 2 = 10 for that is the total number of possible trees for the root RT.

Hence we iterate through the sorted array and figure out the solution considering each element as the root. Below is the algorithm for the same:

NosOfBST(N)
1.if N==0 or N==1
2.return 1;
3.int sum,leftTreeCount,rightTreeCount=0;
4.for k=1 to N
5.leftTreeCount=NosOfBST(k-1);
6.rightTreeCount=NosOfBST(N-k)
7.sum=sum+(leftTreeCount*rightTreeCount)
8.return sum;

Explaining the Algorithm

This is simple, if the number of elements is 0 we return 1 i.e. an empty tree is possible  ie. a tree with null root.If the number of elements is 1 we still return 1 because only one tree is possible and the element is the root of the tree.
For number of elements greater than 1 we iterate through each element of the array and for each element k as root we find the number of trees possible for k-1 elements in the left and the number of trees possible for n-k elements in the right. Now, these two are independent of each other so to find the total trees for a given root, we multiply the number of trees in left and right and add it to the sum.
At the end of the iteration we return the sum total.

Code Snippet

public class NosOfBST {

 static int nosOfUniqueNode = 10;

 public static void main(String[] args) {
  
   System.out.println("Trees possible with elements is "+findNosOfBst(nosOfUniqueNode)); 
  
 }

 public static int findNosOfBst(int n) {
  if (n == 1 || n == 0)
   return 1;
  else {
   int left = 0;
   int right = 0;
   int sum = 0;
   for (int k = 1; k <= n; k++) {
    left = findNosOfBst(k - 1);
    right = findNosOfBst(n - k);
    sum = sum + (left * right);
   }
   return sum;
  }
 }
}

But if we  analyze the complexity , we can see it is near to exponential.Yes we can reduce the time complextity by using dynamic programming (planning) approach.As here we are solving the same sub problem again and again and it is recursive.public class TotalNumberOfBinaryTrees { static int elementCount = 50; static long[] memo = new long[50]; public static void main(String[] args) { for(int i = 1 ; i <= elementCount ; i++){ System.out.println("Trees possible with "+i+ " unique elements "+totalTree(i)); } } public static long totalTree(int n) { if (n == 1 || n == 0) return 1; else { long left = 0; long right = 0; long sum = 0; for (int k = 1; k <= n; k++) { if(memo[k-1] == 0){ memo[k-1] = totalTree(k - 1); } left = memo[k-1]; if(memo[n-k] == 0){ memo[n-k] = totalTree(n - k); } right = memo[n-k]; sum = sum + (left * right); } return sum; } } }