Given n, count the structurally different binary search trees that store exactly the keys 1, 2, ..., n (each once). Two trees are different if their shapes (or, equivalently, the placement of keys) differ. For n = 0 there is exactly one tree: the empty one.
Examples
The 5 trees for n = 3:
1 1 2 3 3
\ \ / \ / /
3 2 1 3 2 1
/ \ / \
2 3 1 2
[1, None, 3, 2] [1, None, 2, None, 3] [2, 1, 3] [3, 2, None, 1] [3, 1, None, None, 2]
Input: n = 3
Output: 5
Input: n = 1
Output: 1
Constraints
0 <= n <= 60(Python integers do not overflow)- O(n^2) time
Goals
- Split the count by the choice of root
- Build the answers bottom-up for every smaller size