A solution via Catalan number

  • 0

    A new thinking to solve this problem is that:
    For a given number of nodes, the number of total unique tree is an Catalan number (https://en.wikipedia.org/wiki/Catalan_number).

    Catalan Number: Cn = choose n from 2n / (1+n)

    And number of unique BST follows this rule.

    public int numTrees(int n) {
            int M = 2*n;
            int N = n;
            double c = 1;
            for(int i = 1; i <= N; i++)
                c = c * (M-N+i)/i;
            return (int) (c/(n+1));

    Runtime: 0ms

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.