Given a sorted integer array, how can binary search trees be generated?

Question

We consider that I have an array [3,18,15,25,26] , how many of it are possible to form binary search trees from it?

Answer 1

Looking at a question related to MicSim, I was still not happy with this, so I started looking at it myself. Here is what I came up with ...

Each tree can be considered as two trees with the parent root node. If you know the number of possible combinations of two child branches separately, then common combinations that have this root node are the product of children's combinations.

We can begin to build a higher counting solution by first allowing shorter counter instances.

I will use C(n) to represent the full possible combinations of n nodes, a Catalan number.

We hope that these two are obvious:

 C(0) = 1 C(1) = 1 

C (2) is also fairly obvious, but it can be built, so let's do it. There are two ways to select the root node. One leaves the counter (left: right) from 1:0 , and the other 0:1 . So, the first possibility is C(1)*C(0) = 1*1 = 1 . And the second is C(0)*C(1) = 1*1 = 1 . Summing them up, we get

 C(2) = 2 

Nothing special. Now let's make 3 nodes. There are 3 ways to select the root node and, therefore, 3 child groups. Your possible groups are: 2:0 , 1:1 and 0:2 .

According to our previous definitions, C(3) can be written as C(2)*C(0) + C(1)*C(1) + C(0)*C(2) = 2*1 + 1*1 + 1*2 = 2+1+2 = 5 .

 C(3) = 5 

4 nodes have child groups 3:0 , 2:1 , 1:2 and 0:3 . So, C(4) can be written as C(3)*C(0) + C(2)*C(1) + C(1)*C(2) + C(0)*C(3) = 5*1 + 2*1 + 1*2 + 1*5 = 5+2+2+5 = 14 .

 C(4) = 14 

Hopefully two things are starting to become apparent. Firstly, it will soon become cumbersome. Secondly, what I described in a rather long way is a representation of a recursive relation on a wiki page.

I don’t know if this helps, but it helped me complete the exercise, so I decided to share it with you. I did not try to recreate the recurrence relation when I started, so it was good that my results corresponded to one of the existing methods.

Answer 2

The possible number of binary search trees that can be created using N keys is given by the Nth directory .

Also see this question: The possible number of binary search trees that can be created using N keys is specified by the Nth Catalon number. Why?

Answer 3

Any of the nodes of the array can be the root of BST, and for each root the number of different search trees is a combination (product) of left and right subarrays. Thus,

 BSTCount(0) = 1 BSTCount(n) = sum_{i = 1}^{n} BSTCount(i-1) * BSTCount(ni) 

You can evaluate this function for the first few n, and then look at the sequence in the On-Line Encyclopedia of Integer Sequences ™ (OEIS) to find the closed form.