0096 - Unique Binary Search Trees

Description (leetcode)

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactlynnodes 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
    }
}