Skip to content

96. Unique Binary Search Trees

Difficulty Topics

Description

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

Solution

unique-binary-search-trees.py
class Solution:
    def numTrees(self, n: int) -> int:

        @cache
        def go(n):
            if n == 0: return 0
            if n == 1: return 1

            res = 0
            for head in range(n):
                res += max(1, go(head)) * max(1, go(n - head - 1))

            return res

        return go(n)