Description
Given an integer n, return the number of structurally unique BST's which has exactly n nodes of unique values from 1 to n.
Examples
Input:
n = 3Output:
5Explanation:
There are 5 unique BSTs with 3 nodes.
Input:
n = 1Output:
1Explanation:
Edge case with minimal input.
Input:
n = 4Output:
14Explanation:
With 4 nodes (1,2,3,4), it is possible to form 14 structurally unique BSTs. For each possible root (1,2,3,4): root=1 gives 1×5=5 trees, root=2 gives 1×2=2 trees, root=3 gives 2×1=2 trees, and root=4 gives 5×1=5 trees, totaling 5+2+2+5=14 unique BSTs.
Constraints
- •
1 ≤ n ≤ 19