Count BST Shapes with Exact Catalan Arithmetic
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the number of structurally different binary search trees containing exactly the distinct keys 1 through `n`. Each key appears once, and a BST places smaller keys in a node's left subtree and larger keys in its right subtree. Return a count rather than constructing the trees.
```cpp
int numTrees(int n);
```
### Examples
```text
Input: n = 2
Output: 2
```
```text
Input: n = 4
Output: 14
```
### Constraints
- `1 <= n <= 19`.
- Different tree shapes count separately; the keys are fixed to 1 through `n`.
Overview: Count structurally distinct BSTs on consecutive keys using exact Catalan arithmetic within the n ≤ 19 source bound.