Number of binary search trees over n elements

Question

I need to find a number of different binary search trees over n elements. I know, that the number of binary search trees over n distinct elements is Catalan number. But what if numbers can repeat? In Binary Search Tree elements of left subtree are less than root, and elements of right subtree are equal or greater than root.

This is my code for calculating a number of different binary search trees over n elements. I calculate this number by modulo 123456789, as it can be really big. Can I simply change it to solve my problem?

#include <algorithm>
#include <vector>
#include <iostream>
#include <limits>

using std::vector;
using std::cin;
using std::cout;
using std::endl;


long long countTreeDP(int nodeNumber) 
{
    vector <vector<long long> > cNumbers;
    for (int i = 0; i < nodeNumber + 2; ++i)
    {
        vector<long long> cur(nodeNumber + 2, 0);
        cNumbers.push_back(cur);
    }
    for (int i = 0; i < nodeNumber + 2; ++i)
    {
        cNumbers[i][0] = 1;
    }

    long long sum = 0;
    for (int i = 1; i < nodeNumber + 1; ++i) 
    {
        sum = 0;
        for (int j = 1; j <= i; ++j) 
        {
            long long numFirst = cNumbers[nodeNumber + 1][i - j] % 123456789;
            long long numSecond = cNumbers[nodeNumber + 1][j - 1] % 123456789;
            cNumbers[j][i] = (numFirst * numSecond) % 123456789;
            sum += cNumbers[j][i];
            sum = sum % 123456789;
        }
        cNumbers[nodeNumber+1][i] = sum;
    }

    return cNumbers[nodeNumber+1][nodeNumber];
}

int main()
{
    vector<long long> nodesValues;
    int size = 0;
    cin >> size;

    for (int i = 0; i < size; ++i)
    {
        long long elem;
        cin >> elem;
        nodesValues.push_back(elem);        
    }

    std::sort(nodesValues.begin(), nodesValues.end());

    int uniqueCount = 0;

    for (int i = 1; i < nodesValues.size(); ++i)
    {
        if (nodesValues[i] != nodesValues[i-1])
            ++uniqueCount;
    }
    cout << countTreeDP(uniqueCount + 1) << endl;
    system("pause");
    return 0;
}

Can you put the meaning of a single cNumbers[a][b] entry into words? If so, does that help you in answering your own question? Would I be correct in assuming that you will provide the sequence of tree node values as input, so that one can check which are distinct and which are equal? — MvG
Each cell p in a column K contains a value which is sum of the left trees and the right trees if pth element is the root. The idea of using matrix cNumbers came from here techieme.in/techieme/count-binary-search-trees . — Ann Orlova

MvG MvG · Accepted Answer · 2013-11-24T15:40:04

I'm assuming that a[i] for 0 ≤ i < n is your sorted array of node values. Here is what I'd do: create a two-dimensional table T such that entry T[x][y] counts the number of search trees for the subsequence x ≤ i < y. You'd initialize it by setting all T[i][i] for 0 ≤ i ≤ n to 1, since the empty sequence has only one search tree, the empty tree.

Now you'd write three nested loops. The outermost loop iterates over sequence length, the middle iterates over possible starting positions, and the innermost iterates over possible tree nodes. Something like

for (int len = 1; len <= n; ++len) {
  for (int pos = 0; pos <= n - len; ++pos) {
    int left = pos, right = pos + len;
    long long cnt = 0;
    for (int root = left; root < right; ++root) {
      if (root > left && a[root] == a[root - 1])
        continue; // duplicate element may not be root
      cnt += T[left][root]*T[root + 1][right];
    }
  }
}

The above would work without the if for the case of distinct elements. If you can have duplicate elements, then an element can only be considered a root of a subtree (according to your definition) if the element before it is strictly less than the element itself, or if it is the first element of the subtree. So the check above skips invalid roots, so in the end T[0][n] would hold your desired count.

I'll leave the modulo arithemtic to you. I'll also leave it to you to compare this idea to the code you wrote yourself, since I don't feel like reading that much uncommented code just now.

Number of binary search trees over n elements

1 Answers