unique binary search trees [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 10 years ago.

开发者_如何学Go Improve this 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???

---

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];
}

---

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.