Unique Binary Search Trees

How it works

Another formula for Catalan numbers uses a recurrence relation: C(n+1) = C(n) * (4n + 2) / (n + 2). This allows us to compute each Catalan number from the previous one with a single multiplication and division.

Steps

1. Initialize res = 1.
2. For i from 0 to n - 1:
   • Multiply res by (4 * i + 2) / (i + 2).
3. Return res as an integer.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting the Base Case for Zero Nodes

When implementing the recursive or DP solution, failing to handle the case where n = 0 leads to incorrect results. An empty tree (zero nodes) has exactly one valid structure (the empty structure), so numTrees(0) must return 1. Without this, the multiplication in the recurrence breaks down since multiplying by zero eliminates valid combinations.

Integer Overflow in Catalan Number Formulas

The Catalan number approach involves multiplying large numbers before dividing. In languages like Java, C++, or Go, intermediate products can overflow standard int types even for moderate values of n. Always use long or long long for intermediate calculations, and be careful about the order of operations to minimize overflow risk.

Confusing Node Count with Node Values

The problem asks for the count of structurally unique BSTs with nodes numbered 1 to n, but the actual values do not matter for counting structures. What matters is how many nodes go in the left versus right subtree. Some solutions incorrectly try to track specific node values rather than just counting nodes, leading to unnecessarily complex code or wrong answers.

class Solution:
    def numTrees(self, n: int) -> int:
        res = 1
        for i in range(n):
            res *= (4 * i + 2) / (i + 2)
        return int(res)

class Solution {
public:
    int numTrees(int n) {
        long long res = 1;
        for (int i = 0; i < n; i++) {
            res *= (4 * i + 2) / (i + 2.0);
        }
        return res;
    }
};