How Many Binary Search Trees With N Nodes

Problem

How Many Binary Search Trees With N Nodes

Write a function that returns the number of distinct binary search trees that can be constructed with n nodes. For the purpose of this exercise, do solve the problem using recursion first even if you see some non-recursive approaches.

Example

{
"n": 3
}

Output:

5

Solution

function how_many_bsts(n) {
    
    if (n === 0) {
        return 1;
    }

    let result = 0;

    for (let i = 1; i <= n; i++) {
        result += how_many_bsts(i - 1) * how_many_bsts(n - i);
    }

    return result;
}

Time and Space Complexity

Time: O(Catalan number(n)).
Auxiliary space: O(n).
Total space: O(n).