Skip to content

96. Unique Binary Search Trees

Math Dynamic Programming Tree Binary Search Tree Binary Tree

Problem - 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:

  • 1 <= n <= 19

Solutions

1
2
3
4
5
6
7
8
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [1] + [0] * n
        for i in range(n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - j - 1]

        return dp[-1]

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.7 MB (50.43%)