367. How many structurally different binary search trees can be built from n distinct keys?
MediumDynamic programming
Technical
Show model answer
Choose the root as the (i+1)-th smallest key: i keys go left and n − 1 − i go right, and the subtrees are independent. So C(0) = 1 and C(n) = Σ C(i)·C(n − 1 − i) for i from 0 to n − 1, the Catalan numbers 1, 1, 2, 5, 14, 42, 132, ... The DP takes O(n²) time and O(n) space.
The closed form is C(n) = (2n choose n) / (n + 1), computable in O(n) with the ratio C(n+1) = C(n) · 2(2n + 1) / (n + 2). The same numbers count binary trees with n nodes, ways to fully parenthesise n + 1 factors, balanced bracket strings of length 2n, and triangulations of a polygon with n + 2 sides.