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

Bloom Filters By Example

In this post we will discuss about bloom filter and its use case.Let's create a scenario like this first.
Assume there is cycle stand in our college.And the stand has 1000 slots for parking the cycles.And usually  one slot can have 4 cycles.So definitely that stand has capacity to have 4000 cycles.And it is very well known  that Mr. Akash keeps his cycle in slot no 1 every day.

So if we want to know if Akash is present in college today,we just check slot no 1 and if there is any cycle available there , we say yes Akash is present in college.But it is not hundred percent correct.As we said above each slot can have four cycles,it may be possible that cycle present in slot no 1 may not belongs to Akash.

So here a case arrises, which is false positive.But if no cycle is there in slot no 1, we say that definitely Akash is absent today.So there is no chance of false negative.That is we never say that Akash is absent today in case of his presence in college.

Bloom filter is a simple hash based  filter works  on the same principle.It allows to store elements and help us to quickly  identify many (not all) elements those are not present.Sometimes we can say that Akash is not in the college(if no cycle is there in slot 1).

Use Case:

Suppose we are going to create an anti virus software, which will maintain the list of malicious site and a list of know viruses.A naive approach is to maintain data structure to hold the details of all the malicious programmes.A problem with this approach is that it may consume a considerable amount of memory. If you know of a million malicious programmes, and programmes  need  an average of 10 bytes to store, then you need 10 megabytes of storage. That’s definitely an overhead . Is there any efficient way?Yes there  is.

Implementation Details:

We will do two things with bloom filter
1.insert an element in the filter.
2.Test an element if it is a member of bloom filter.

Bloom filter is a probabilistic data structure,that is not deterministic.We will came to know the reason in a while.

Let's take a bit array of size m.Initialize each position to zero.The idea here is that we choose k hash functions whose max value will be within the range 0 to m.Here k is constant such that k
To test for an element (whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions is 0, the element is definitely not in the set. if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have been set by chance to 1 during the insertion of other elements, which results  false positive.

Deletion of elements are not allowed due to obvious reasons.Suppose we want to delete an element then defintely we need to set any of the  k bit positions generated by k hash functions for that element to 0.But there will be a chance that bit which we are going to set to 0 may be the result of some other elements.


To add an element in the filter simply pass that element to the k hash functions.Now we will get k different values between 0 to m-1 i.e we ll get k different array positions.Mark these positions to 1.Note that here we are not putting the exact hash value in array we are simply marking that position to 1.
As false negatives are not allowed in Bloom filter, we can't delete the elements from it.

Applications of Bloom Filter:

1.Cassandra uses bloom filters to save IO when performing a key lookup: each SSTable has a bloom filter associated with it that Cassandra checks before doing any disk seeks.
2.The Google Chrome web browser use a Bloom filter to identify malicious URLs. Any URL was first checked against a local Bloom filter, and only if the Bloom filter returned a positive result was a full check of the URL performed (and the user warned, if that too returned a positive result).


Although the Bloom Filter is a data structure ,it is called a filter because because it often used as a first pass to filter out elements of a data set that dont match a certain criteria.

Please refer wikipedia  for more applications and detailed explanations.