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

Consider each number 'i' (0 to n) as a potential root. Recursively count BSTs for elements less than 'i' (left subtree, 'x'), and count BSTs for elements greater than 'i' (right subtree, 'y'). As x is independent from y, multiply 'x' and 'y' to get BSTs with 'i' as root. Sum the results from all 'i' to get the total BST count.

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));