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

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs