Write num_trees(n: int) -> int returning how many structurally different binary search trees store exactly the keys 1..n.
Constraints: 1 <= n <= 19.
num_trees(1) # 1
num_trees(3) # 5
num_trees(4) # 14
Plain recursion over every tree is far too slow for n = 19; aim for about O(n^2).
Show hint
Choose the root first. Given the root, which keys go left and which go right, and does anything other than the number of keys on each side matter? That gives a recurrence you can fill as a table.