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; } } }

Total number of possible Binary Search Trees with n nodes

Introduction

As we know,there can be more than one BST possible with a given set of elements. This article addresses  about it. How many Binary Search Trees are possible for a given set of N elements? Here we are only discussing the concern when the elements given  are unique. Hence, we will count binary search trees created from N unique elements.

  Solving the problem

we will solve such problems starting from the known facts, there is no point creating all possible BSTs with the N given elements and then answer. Let us understand it in a bottom up approach. What does the bottom up approach suggests?
Question 1: Can we say the answer for N = 0?
Question 2: Can we say the answer for N = 1?
Question 3: Can we say the answer for N = 2?
Question 4: Is there any relation in the patterns?
Question 5: Is there a solution for N = k which can contribute to the solution of N = k+j,where j is some number >=1 ?
If  answer of these questions are yes ,then we can say that this is a programming problem which can be solved either by recursion or Dynamic Programming. Because this problem is satisfying all the criteria of dynamic programming.
So let us take a set of numbers, fairly randomly distributed so that we get a beautiful BST. We will answer all the questions listed above:

Let's assume we are given  9 nodes .

Answer 1: When N = 0 then there is no tree or I can say an empty tree,or we can say a tree with root is null, hence total number of possible BSTs is 1
Answer 2: When N = 1 then there is only one tree, and that is the root as below, so the number of trees = 1




Answer 3: When N = 2 then there are two trees possible:
a) With 6 as root and
b) With 10 as root
So the number of trees = 2

Answer 4: When N = 3 then we will have following options:
a) With 6 as root
b) With 10 as root and
c) With 13 as root.
Then we see that when 6 is the root then 10 and 13 lie on the right side of the root. That means there are as many possibilities as we had with N = 2 same as the Answer 3.
Similarly when 10 is the root, 6 lies in the left and 13 on the right of the root. So, we have those many possibilities on each side as many we had when N = 1 same as the Answer 2. But we must also realize that for each possibility of left we can have all the possibility in the right or vice versa. In simple words the number of trees formed from the elements in the right is independent of the number of trees formed from the elements in the left. So the total number of trees will be a product of the total left trees and total right trees.
To explain it more, for each tree of the left we can have all possible trees in the right.
Similarly when 13 is the root, 6 and 10 lie on the left side of the root, Than means there are as many possibilities as we had with N = 2 same as Answer 3.
Hence total number of trees possible is 2 + 1 * 1 + 2 = 5. So there is a pattern.

Answer 5: We also saw in answer 4 that the solutions of the smaller problems (for lower values of N) can add up in solving the bigger problem (with higher values of N).
Now assume we are given N = 4.  how do we solve the problem , it will be same as the one we solved in Answer 4.
We will consider each element as the root once and so we will come up with 4 cases, then we find the number of trees possible in each case and add up total number of trees from each case.

Generating the Algorithm and Code snippet -Part2