Description (leetcode)

Given an integer n, return *the number of structurally unique **BST’*s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3

Output: 5

Example 2:

Input: n = 1

Output: 1

Constraints:

  • 1 <= n <= 19

submission

impl Solution {
    pub fn num_trees(n: i32) -> i32 {
        // Nth catalan number
        (0..(n as i64)).fold(1, |c, i| c * 2 * (2 * i + 1) / (i + 2)) as i32
    }
}