Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1, ... , n?
For example,
Given n = 3, there are a total of 5 unique BST's.
Solution:
If root is 1 or n, then the left (or right) subtree is empty; another subtree stores n - 1 values
If root is between 2 and n - 1, i.e., 1 < i < n, then the left subtree stores i - 1 values (1, ... , i - 1), the right subtree stores n - i values (i + 1, ... , n)
Suppose the number of unique BST's that store values 1, ... , n is T(n), then
T(n) = 2 * T(n - 1) + sum^{n - 1}_{i = 2} T(i - 1) * T(n - i)
This number is also known as Catalan number
The following code passes LeetCode online large judge
Or, we can define T(0) = 1, then T(n) = sum^{n-1}_{i=0} T(i) T(n-1-i).
Java version:
Comments
Post a Comment