The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?

Fireblend_9506 0
Viewed 12791

This has been bothering me for a while. I know that given N keys to arrange in the form of a binary search tree, the possible number of trees that can be created correspond to the Nth number from the Catalan sequence.

I have been trying to determine why this is; unable to find anything that might even attempt to explain it intuitively I resort to the collective knowledge of SO. I found other ways to calculate the number of possible trees, but they seemed less intuitive and no explanation was offered beyond how to use it. Plus the wiki page (that link above) even shows an image of the possible tree formations with 3 keys, which would lead me to think there's a nice and neat explanation to be heard (which is, needless to say, not included in the article).

Thanks in advance!

binary-tree binary-search tree math
4 Answers

Well here is the recursive solution to count the trees...

int countTrees(int numkeys){

if(numkeys > 1){
    int i =1;
    int sum=0;

    for(i = 1; i <= numkeys; i++){

        int lcount = countTrees(i-1);
        int rcount = countTrees(numkeys-i);
        sum += lcount*rcount;
    }
    return(sum);
}else
    return(1);
}
user_2473360

I have same desire to know why it happens to be the Catalan number; Just forget about what Catalan number is for now and find out the formula to calculate the number of unique binary trees for n nodes.

Let C(n) be the number of possible binary trees with given n vertices, C(0) = 1, now consider C(n) when n > 0, since there must be a root node for every binary tree, so the problem now turns to be how many possible binary trees we can generate on both left and right child of the root node with n – 1 vertices.

To find the answer, we have to enumerate all possible trees on both sides.

C(n) = C(0) * C(n - 1) + C(1) * C(n - 2) + ... + C(n – 2) * C(1) + C(n - 1) * C(0)

enter image description here

And that's the recursion form of the Catalan numbers. It's easy to accept it once I see this recursion form instead the formula in Wikipedia.

(Most of texts from https://coldfunction.com/mgen/p/3r)

user_15321460
Related