unique binary search trees

Question

given a set of integers find out how many unique binary search trees can be constructed out of it???

according to me the answer depends on the size of the integer set.. if the size of the set integer is n.. then "n" unique binary search trees can be made out of it..

am not sure about the answer.. am i right???

By "the number of unique integers," do you mean "the number of unique integers in the set?" The mathematical definition of a set does not allow for duplicate elements, so "the number of unique integers in the set" is the same thing as the size of the set. (If that's not what you mean... well, there are an infinite number of integers.) — Matt Ball, May 31 '11 at 17:01
possible duplicate of [With ' N ' no of nodes, how many different Binary and Binary Search Trees possible ?](http://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possibl) — Matt Ball, May 31 '11 at 17:21

score 2 · Answer 1 · edited Sep 23 '12 at 11:45

This could be solved by using dynamic programming.

numTrees(i+1)=append the last node to the rightmost leaf of bst(i)[numTrees(i)] +
              append the last node as the root of bst(i)[numTrees(i)] +
              insert the last node as non-leaf node sum(k=1...i)(bst(k-1)*bst(i-k)

so it is o(n^2) solution.

public int numTrees(int n) {
    if(n == 0 || n == 1 || n == 2)
        return n;
    int bst[] = new int[n+1];
    bst[0] = 1;
    bst[1] = 1;
    bst[2] = 2;
    for (int i=3; i<=n; i++) {
        for (int j=1; j<i-1; j++) {
            bst[i] += bst[j]*bst[i-1-j];
        }
        bst[i] += 2*bst[i-1];
    }
    return bst[n];
}

score 1 · Answer 2 · answered May 31 '11 at 17:24

The number is C_n where C_n is the nth Catalan Number. The value can be defined recursively by picking any one of the n nodes as the root and then taking all possible ways of organizing the left and right subtrees of the root, leading to the following recurrence relation:

C_n = sum_{i = 0}^{n - 1} C_i * C_{n - 1 - i},

where C_0 = 1.

unique binary search trees

2 Answers2