How many different trees
Count the binary search trees that can hold the values 1 to n, by choosing each value as the root and multiplying the counts for the smaller and larger values. About 16 minutes.
Choose a root, then multiply
How many binary search trees hold the values 1 to n? Pick one value r as the root. In a search tree, the r minus 1 smaller values must go on the left and the n minus r larger values on the right.
Any shape for the left can be paired with any shape for the right, so the number of trees with root r is the number of left shapes times the number of right shapes. The answer sums this over every choice of r.
total = 0
for root in range(1, n + 1):
total += left_ways * right_waysOne value: a single root with two empty sides. 1 × 1 = 1 shape.
Build a table from small to large
The count for a set of values depends only on how many values there are. So store the counts for 0 values, 1 value, 2 values and so on in a table, filling it from small to large, since each count uses only smaller ones.
An empty tree counts as exactly one shape. This is what makes the multiplication work when one side has no values. These numbers are known as the Catalan numbers: 1, 1, 2, 5, 14, 42, and so on.
ways = [0] * (n + 1) ways[0] = 1
How many search trees hold the values 1, 2, 3 with 2 as the root?
- A1
- B2
- C5
Show the answer
1. 1 must be on the left and 3 on the right, and each side has one shape.
Unique binary search trees
Given an integer n, return the number of structurally different binary search trees that store exactly the values 1 to n, each once.
n = 3 → 5
0 ≤ n ≤ 19