Unique BST Shapes
Problem
Count the structurally different binary search trees that can hold the values 1 through n, each value used exactly once. Two trees differ when their shapes differ, so the same values arranged differently count separately. For n equal to 0 the answer counts the single empty tree.
Examples
Input: n = 3
Output: 5
Why: each of the three values can be the root, and the root 2 allows only one shapeInput: n = 1
Output: 1
Why: a single value has exactly one treeInput: n = 0
Output: 1
Why: edge case, the empty tree is one valid shapeHints
0 / 3
Fix the root first. The search property then decides, with no freedom at all, which values must live on the left and which on the right.
If the root is the k-th smallest value, the left subtree holds k-1 values and the right subtree holds the rest, and the two sides are chosen independently of each other.
That makes the count for a given size a sum over every possible root of a product of two smaller counts. Fill a table from size zero upwards, treating the empty subtree as one shape, and read the answer at size n.
Solution
Choosing the root splits the values deterministically: everything smaller goes left and everything larger goes right, so the count for a size is a sum over roots of left count times right count. Only the sizes of the two sides matter, never the actual values, which is why one table indexed by size suffices. Seeding size zero with one shape makes the empty subtree behave correctly inside every product. Time is O(n squared) for the double loop, and space is O(n).
def count_bst_shapes(n):
ways = [0] * (n + 1)
ways[0] = 1 # the empty tree counts as one shape
for size in range(1, n + 1):
for left in range(size): # the root leaves `left` values on its left
ways[size] += ways[left] * ways[size - 1 - left]
return ways[n]
print(count_bst_shapes(3)) # -> 5
print(count_bst_shapes(1)) # -> 1
print(count_bst_shapes(0)) # -> 1Stuck on the idea rather than the code? BST Basics covers it.