Medium

Unique Binary Search Trees

LAB

Return the number of structurally unique BSTs storing values 1 through n.

EXAMPLES

Example 1

Input
{
  "n": 3
}

Output
5

FUNCTION SHAPE

n: int→int

SOLUTION NOTE

Catalan numbers. For each root i, left subtree has i-1 nodes, right has n-i nodes. Multiply and sum.

Reveal reference solution +

pythonREFERENCE

def numTrees(self, n: int) -> int:
    @cache
    def dp(n):
        if n <= 1:
            return 1
        total = 0
        for root in range(1, n + 1):
            left = root - 1
            right = n - root
            total += dp(left) * dp(right)
        return total

    return dp(n)

TimeO(n²)

SpaceO(n)

Open on LeetCode ↗