Finding number of postorder BSTs permutations

Question

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.

Answer 1

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:

postorder	valid BST?
1 2 3 4	yes
1 2 4 3	yes
1 3 2 4	yes
1 3 4 2	no
1 4 2 3	no
1 4 3 2	no
2 1 3 4	yes
2 1 4 3	yes
2 3 1 4	yes
2 3 4 1	yes
2 4 1 3	no
2 4 3 1	yes
3 1 2 4	no
3 1 4 2	yes
3 2 1 4	yes
3 2 4 1	yes
3 4 1 2	no
3 4 2 1	yes
4 1 2 3	no
4 1 3 2	yes
4 2 1 3	no
4 2 3 1	no
4 3 1 2	no
4 3 2 1	yes

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