A root splits the count in two
Every choice of root leaves a smaller left-count and a smaller right-count, multiplied together. About 13 minutes.
Pick the root, and both sides are decided
How many differently shaped search trees can hold the numbers 1, 2 and 3? A search tree keeps smaller numbers on the left and bigger ones on the right.
Choose which number sits at the top. Everything smaller must go left, everything bigger must go right. With 2 on top, the 1 goes left and the 3 goes right. And the shape of the left side has nothing to do with the shape of the right.
Multiply the sides, add the roots
For one choice of root, any left shape can go with any right shape, like choosing a shirt and a pair of trousers: the options multiply. Different roots give completely different trees, so those counts add.
Only the size of each side matters, not which numbers are in it. So the count for 3 numbers uses the counts for 0, 1 and 2 numbers, and comes out at 2 + 1 + 2 = 5.
ways = [1] + [0] * n ways[size] += ways[left] * ways[right]
An empty tree is one shape, and so is a single node.
With 1, 2 and 3 and the 2 on top, one number goes on each side. Each side has 1 possible shape. How many trees have 2 on top?
- A1
- B2
- C3
Show the answer
1. 1 left shape times 1 right shape: 1 tree.
Unique binary search trees
Return how many differently shaped binary search trees can hold exactly the n values 1 to n, each once.
n = 3 → 5
0 ≤ n ≤ 30 · return a long