Count the Distinct Binary Search Tree Shapes for Keys 1 to n
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
Given an integer `n`, count how many structurally different binary search trees can hold the keys `1, 2, ..., n`, with each key used exactly once.
Two trees count as different when their shapes differ. For a fixed set of keys, the search-tree ordering determines which key sits at each node of a given shape, so counting distinct trees is the same as counting distinct shapes.
### Function Signature
```python
def count_bst_shapes(n: int) -> int:
```
### Rules
- In a binary search tree, every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
- Each tree must contain all `n` keys.
- Return the number of distinct trees as an integer.
### Constraints
- `1 <= n <= 19`
- The largest answer, for `n = 19`, is 1,767,263,190, which fits in a signed 32-bit integer.
### Examples
**Example 1**
```text
Input: n = 3
Output: 5
```
The keys 1, 2 and 3 can be arranged into five different valid search trees.
**Example 2**
```text
Input: n = 1
Output: 1
```
**Example 3**
```text
Input: n = 4
Output: 14
```
Overview: Count how many structurally different binary search trees can store the keys 1 through n exactly once, for n up to 19. It tests reasoning about how tree shapes decompose and counting combinatorial structures efficiently instead of building every tree.
Read the full Amazon Software Engineer interview experience this question came from
