Unique Binary Search Trees and Catalan Numbers

The goal: G(n) = sum of each number from 1 to n as root F(1,n) + F(2,n) + F(3,n) + … + F(n,n)

F(i,n) = G(i-1) * G(n-i) - multiply left and right subtree counts (the sum n-1 represents nodes except the root)

This formula also calculates Catalan numbers.

int numTrees(int n) {
    vector<int> dp(n+1, 0);
    dp[0]=dp[1]=1;

    for(int i=2;i<=n;++i) {
        for(int j=1;j<=i;++j) {
            dp[i]+=dp[j-1]*dp[i-j];
        }
    }

    return dp[n];
}

Catalan Numbers

Recursive sequence pattern:

• n = 0: 1
• n = 1: 1
• n = 2: 2
• n = 3: 5
• n = 4: 14
• n = 5: 42
• n = 6: 132

These all reduce to stack push/pop problems.

Stack ordering:

• How many different push/pop sequences for n items?
• How many different train station entry/exit orders for n trains?

Parentheses:

• How many ways to match n pairs of parentheses?
• How many multiplication orders for n+1 numbers? (need n pairs of parentheses)

Binary trees:

• How many different binary trees with n nodes?
• Given preorder traversal, how many possible inorder traversals exist?

Queue ordering:

• 2n people line up for theater tickets. Each ticket costs $5. n people have only $5 bills, n people have only $10 bills (must get change). Theater starts with no change. How many ticket purchase orders let everyone buy tickets successfully? This becomes a parentheses matching problem.

#math