Count Unique BSTs

Problem

Return the number of structurally unique binary search trees that store the values 1 through n.

This is the n-th Catalan number, computed with the multiplicative formula C(2n, n) // (n + 1). n = 0 counts the empty tree.

Hint

Choosing root r splits the problem into counts for r - 1 and n - r left and right subtrees.

case 1

in: [0]

expected: 1

case 2

in: [1]

expected: 1

case 3

in: [3]

expected: 5

case 4

in: [5]

expected: 42

case 5

in: [10]

expected: 16796

Starter codePython

def count_unique_bsts(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor