Count Binary Search Trees created from N unique elements

Introduction

This is the third article for Binary Search Trees, to read more about the previous article, please check the topic Binary Search Tree Basics – a detailed discussion. To get updates on the coming articles in the series, please use the Subscribe feature on the right panel.

Purpose of article

This article explains few more aspects of binary search tree (BST). In the last article we learnt to construct a BST and then we revisited our technique to construct a better BST with the same. So this means that there can be more than one BST possible with a given set of elements. This article addresses the question How many Binary Search Trees are possible for a given set of N elements? Please note that the question says Set and not List, that means we are only addressing the concern when the elements given are unique. HEnce, we will count binary search trees created from N unique elements.

Approaching the problem

I mostly like to 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: Do we know the answer for N = 0?
Question 2: Do we know the answer for N = 1?
Question 3: Do we know the answer for N = 2?
Question 4: Is there any relation of pattern?
Question 5: Is there a solution for N = i which can contribute to the solution of N = k where i < k ?

If these questions are answered in a positive manner 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 the two hall marks of dynamic programming and you can find them in the article where I discussed dynamic programming in much detail.

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:
array2
Answer 1: When N = 0 then there is no tree or I can say an empty tree, 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
root
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
2tree
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 right. 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.
5tree
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 = 8, so 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 8 cases, then we find the number of trees possible in each case and add up total number of trees from each case. That would be the answer.

  • anonymous

    It’s a waste of memory space to store the matrix. One dimensional array storing the treeCount[i] (the last row in your table) is all you need.

  • Nikhil

    for(j=1;j<i;j++)
    sum[i]+=sum[i-1] * sum[i-j]

    • Nikhil

      sum[j-1] * sum[i-j]