Finding number of postorder BSTs permutations

I’m dealing with a problem which says:
find permutations from 1 to n of BSTs (postorder traversal).
for example for n = 3: we have 6! – 1 = 5 permutations because (3 1 2) is not a BST postorder.

I Wrote an algorithm for this, for example for n = 4:

In total we have 3!+2!+2!+3! = 16

I’ve written this piece of code using this algorithm to calculate number of permutations from 1 to n:

int calcPerm(int n)
{
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        sum += (fact(n-1-i) * fact(i));
    }
    return sum;
}

I know for some n, 1 <= n <= 20 it gives me a wrong answer and I don’t know why its not working.
Any help would be appreciated.

Factorials grow quickly out of range of a 32-bit integer. But taking a step back, that formula (algorithm) is not correct. You write:

Wrote an algorithm for this, for example for n = 4: […] In total we have 3!+2!+2!+3! = 16

But 16 is not the correct outcome for 𝑛 = 4. It should be 14.

Here is a table of all possible postorders, and whether they can be a BST or not:

So although your algorithm gives correct results for 𝑛 < 4, it starts overshooting the expected outcome from 4 onwards.

Catalan numbers

The number of postorders that can describe a BST really corresponds to the number of shapes a binary tree with 𝑛 nodes can have. Once the shape of the tree is established, there is only one way to label the nodes with the given numbers so that it would be a BST. And so this also uniquely corresponds to a postorder.

The number of shapes of a binary tree is given by Catalan numbers.

We can use an incremental formula to calculate the first 21 of them, and for 𝑛 = 20, the result is 6,564,120,420. An int does not have enough range for this, so you should use long instead.

Code:

#include <iostream>
#include <vector>

std::vector<long> getCatalans(const int n) {
    std::vector<long> results = {1};
    long c = 1;
    for (int i = 1; i <= n; ++i) {
        c = 2*(2*i - 1) * c / (i + 1);
        results.push_back(c);
    }
    return results;
}

int main() {
    std::vector<long> catalans = getCatalans(20);
    for (int n = 1; n <= 20; n++) {
        std::cout << n << ". " << catalans[n] << std::endl;
    }
}

Output:

1. 1
2. 2
3. 5
4. 14
5. 42
6. 132
7. 429
8. 1430
9. 4862
10. 16796
11. 58786
12. 208012
13. 742900
14. 2674440
15. 9694845
16. 35357670
17. 129644790
18. 477638700
19. 1767263190
20. 6564120420

FYI, the number of BSTs with nodes numbered 1 to n (inclusive) is given by the nth Catalan number:

Source: https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1214/sections/section8/

#include <iostream>
#include <vector>

unsigned long long CatalanRecursive(unsigned int n) {
  if (n <= 1) return 1;
  unsigned long long res = 0;
  for (unsigned int i = 0; i < n; i++)
    res += CatalanRecursive(i) * CatalanRecursive(n - i - 1);
  return res;
}

unsigned long long CatalanDynamicProgramming(unsigned int n) {
  std::vector<unsigned long long> catalan(n + 1, 0);
  catalan[0] = catalan[1] = 1;
  for (unsigned int i = 2; i <= n; i++)
    for (unsigned int j = 0; j < i; j++)
      catalan[i] += catalan[j] * catalan[i - j - 1];
  return catalan[n];
}

int main() {
  unsigned int n = 3;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  n = 4;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  n = 5;
  std::cout << "CatalanRecursive(" << n << ") = " << CatalanRecursive(n) << '\n';
  std::cout << "CatalanDynamicProgramming(" << n << ") = " << CatalanDynamicProgramming(n) << '\n';
  return 0;
}

Output:

CatalanRecursive(3) = 5
CatalanDynamicProgramming(3) = 5
CatalanRecursive(4) = 14
CatalanDynamicProgramming(4) = 14
CatalanRecursive(5) = 42
CatalanDynamicProgramming(5) = 42