LeetCode-in-All

96. Unique Binary Search Trees

Medium

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:

Solution

# @param {Integer} n
# @return {Integer}
def num_trees(n)
  result = 1

  for i in 0...n
    result *= (2 * n - i)
    result /= (i + 1)
  end

  result /= (n + 1)
  result.to_i
end