Unique Binary Search Trees

The number of unique Binary Search Trees (BSTs) for a given number n can be calculated using the concept of Catalan numbers. The n-th Catalan number can be found using the formula:

[ C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)! \cdot n!} ]

Here’s a function to calculate the number of unique BSTs for a given n:

1
2
3
4
5
6
7
8
9

class Solution:
    def numTrees(self, n: int) -> int:
        # Using the formula for Catalan number
        result = 1
        for i in range(0, n):
            result *= (2 * n - i)
            result //= (i + 1)

        return result // (n + 1)

This code snippet calculates the number of unique BSTs by implementing the formula for Catalan numbers directly. It uses a loop to calculate the product and divides by (n + 1) at the end to find the n-th Catalan number.

The time complexity of this function is ( O(n) ), and the space complexity is ( O(1) ).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# @param {Integer} n
# @return {Integer}
def num_trees(n)
  c = 1
  for i in (0...n)
     c = c * 2 * (2 * i + 1)/ (i + 2) 
  end

  return c
end

title: Unique Binary Search Trees tags: catalan-number

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

Implementation

Catalan number formula calculates the answer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# @param {Integer} n
# @return {Integer}
def num_trees(n)
  c = 1
  
  for i in (0...n)
    c = c * 2 * (2 * i + 1)/ (i + 2) 
  end
    
  return c
end