Number of unique BST with N keys

Given an integer n, count the total number of unique BSTs that can be made using values from 1 to n.

Hint

This algorithm operates by considering each number 'i' within a given range (0 to n) as the 'root' of a tree. For each 'i', the process is recursively applied to:

The number of ways ('x') to arrange elements smaller than 'i'
The number of ways ('y') to arrange elements larger than 'i'

The number of arrangements possible for 'i' as the root is calculated as the product of 'x' and 'y' (x * y), due to x is independent from y. The total number of arrangements across all possible root values ('i') is obtained by summing the number of arrangements for each 'i' within the range (0 to n).

Python
Javascript

# Python implementation

def C(n):
  if n <= 1:
    return 1

  result = 0

  for i in range(n):
    result += C(i) * C(n - 1 - i)

  return result

n = 5

print(C(n))

// Javascript implementation

function C(n) {
  if (n <= 1) {
    return 1;
  }

  let result = 0;

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

  return result;
}

const n = 5;

console.log(C(n));