96. Unique Binary Search Trees
You are given a single integer n. Imagine every binary search tree you could build that stores each of the values 1 through n exactly once. Your function receives n and returns how many structurally distinct BSTs are possible.
Two trees are distinct when their shapes differ anywhere. Because the BST ordering rule fixes where every value must live once the shape is chosen, counting shapes and counting labeled BSTs are the same thing here.
For n = 3 there are exactly five such trees (see the figure).
Example 1:
Input: n = 3
Output: 5
Explanation: With values 1, 2, 3 you can build five different tree shapes: two rooted at 1, one rooted at 2, and two rooted at 3.
Example 2:
Input: n = 1
Output: 1
Explanation: A single node is the only possible tree.
Constraints:
- 1 ≤ n ≤ 19
- The answer always fits in a 64-bit signed integer.
Hints:
Pick which value sits at the root. Every smaller value is forced into the left subtree and every larger value into the right — so both sides become smaller copies of the original question.
Let G(k) be the count for k values. A root that leaves `L` values on the left contributes G(L) · G(k − 1 − L). Summing over all L gives the Catalan recurrence; memoize or fill a table so each G(k) is computed once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3
Expected output: 5