The problem
A binary search tree (TREE-3) can hold the same keys in many shapes. Return how many different binary search trees hold the keys 1, 2, …, n. Two trees are different if their shapes are different.
shapes(3) # 5
shapes(0) # 1: the empty tree
shapes(4) # 14
A formula for this count exists, so math.comb, math.factorial and math.perm are switched off. Work it out from smaller counts.
Limits
nis from 0 to 200. The answers have up to 117 digits; Python’s whole numbers hold them exactly.- Memoised recursion is fine here: it goes at most 200 calls deep.
Builds on DYNP-1 Overlapping subproblems.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
9 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | No keys | Not run | |
| 3 | One key | Not run | |
| 4 | Two keys | Not run | |
| 5 | Four keys | Not run | |
| 6 | Ten keys | Not run | |
| 7 | 25 keys | Not run | |
| 8 | 120 keys | Not run | |
| 9 | 200 keys | Not run |