LeetCode Unique Binary Search Trees: O(N) Time and O(1) Space by Catalan Number

Overview

LeetCode Unique Binary Search Trees could be solved by Dynamic Programming but O(N) Time and O(1) Space exists with a closed form called Catalan Number.

LeetCode 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.

1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis: O(N) Time and O(1) Space by Catalan Number

1) Dynamic programming, suppose  F(N) is the number of total unique BST’s that store values 1…n, then we have F(N) = \sum F(i-1) * F(N-i) where i = 1, 2, … N.  Use the recursive definition and memorizing, it could be solved. The following code implements this idea with O(N^2) time and O(N) space cost. It is accepted by LeetCode OJ to pass this Unique Binary Search Trees problem:

class Solution {
    public:

        int numTrees(int n) {
            if (n <= 1) return 1;

            int *dp = new int[n + 1];

            dp[0] = dp[1] = 1;

            for (int i = 2; i <= n; ++i) {
                dp[i] = 0;
                for (int j = 1; j <= i; ++j)
                    dp[i] += dp[i - j] * dp[j - 1];
            }
            int ret = dp[n];
            delete [] dp;
            return ret;
        }
};

2) Catalan number solution with O(N) time and O(1). Well, with some mathematical background, it actually can be proved that, with the recursive formula in (1), the results of f(N) actually has a closed form expression:

catalan2.png

And further, it could be proved:

C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n,

This is called Catalan Number. And by the above formula, we can write the following O(N) time and O(1) Space code to pass this Unique Binary Search Tree problem on LeetCode OJ:

int numTrees(int n) {
    if (n <= 1)
         return 1;

    int ret = 1;
    for (int i = 1; i <= n; ++i)
        ret = ret * 2 * (2 * i - 1) / (i + 1);

    return ret;
}

Remarks:

  1. The LeetCode OJ actually is very weak on this problem, as long as you do not simulate all the unique trees, a recursive implementation without memorizing can even pass the OJ
  2. The Catalan Number approach is non-trivial and requires strong mathematical background.
  3. References for the Catalan Number: “Binary Trees” and Wiki: “Catalan number

Summary

LeetCode Unique Binary Search Trees could be solved by Dynamic Programming but O(N) Time and O(1) Space exists with a closed form called Catalan Number.

Written on May 22, 2013