online advertising

Wednesday, April 8, 2015

LeetCode OJ - Unique Binary Search Trees

Problem:

Please find the problem here.

Solution:

This is the first time I tried to write the blog before I have got the code accepted, because I needed this workspace to write the derivation.

Denote $ C(n) $ be the number of unique binary search trees with $ n $ nodes. There is exactly 1 empty tree, so $ C(0) = 1 $. The number of unique binary search trees for $ n $ nodes can be computed by selecting one node as the root, and then multiply the number of trees on the left by the number of trees on the right, in formula, it look like this $ C(n) = \sum\limits_{i = 0}^{n - 1}{C(i) \times C(n - 1 - i)} $.

One could write the code for this directly, it will be easy to write, you will need $ O(n) $ space for storing all those number and $ O(n^2) $ time to compute the value, not bad at all if $ n $ is small.

But let's challenge ourselves, is it possible to just give a formula if $ C(n) $ without going through the previous values?

The sum of two values such that their indexes has equal sums seems very similar to what one would do in multiplication, so let's try out the generating function approach.

Let $ C(z) = \sum\limits_{p = 0}^{\infty}{C(p)z^p} $, and let multiply them together.

$ \begin{eqnarray*} C(z)^2 &=& \sum\limits_{p = 0}^{\infty}{C(p)z^p} \sum\limits_{q = 0}^{\infty}{C(q)z^q} \\ &=& \sum\limits_{p = 0}^{\infty}{\sum\limits_{q = 0}^{\infty}{C(p)z^p C(q)z^q}} \\ &=& \sum\limits_{p = 0}^{\infty}{\sum\limits_{q = 0}^{\infty}{C(p)C(q)z^{p+q}}} \\ &=& \sum\limits_{n = 0}^{\infty}{\sum\limits_{r = 0}^{n}{C(r)C(n-r)z^{n}}} \\ &=& \sum\limits_{n = 0}^{\infty}{C(n+1)z^{n}} \\ zC(z)^2 + 1 &=& 1 + z\sum\limits_{n = 0}^{\infty}{C(n+1)z^{n}} \\ &=& 1 + \sum\limits_{n = 0}^{\infty}{C(n+1)z^{n+1}} \\ &=& 1 + \sum\limits_{n = 1}^{\infty}{C(n)z^{n}} \\ &=& \sum\limits_{n = 0}^{\infty}{C(n)z^{n}} \\ &=& C(z) \end{eqnarray*} $

The whole point of doing the exercise above is to determine $ C(z) $, now we can solve $ C(z) $ as follows:

$ \begin{eqnarray*} zC(z)^2 - C(z) + 1 &=& 0 \\ C(z) &=& \frac{1 \pm \sqrt{1 - 4z}}{2z} \\ \end{eqnarray*} $

The reason why we have more than one solutions for $ C(z) $ is simply because we squared it in the first place. It make no sense to have negative coefficients, so we decide to solution that lead to positive coefficients. Last but not least, we expand $ C(z) $ using Taylor's expansion to recover $ C(n) $, to do that, we need to differentiate the expression $ n $ times, so let's do that.

$ \begin{eqnarray*} \frac{d^n}{dz^n} (1-4z)^{\frac{1}{2}} &=& \frac{d^{n-1}}{dz^{n-1}} \frac{1}{2}(-4)^1(1-4z)^{\frac{-1}{2}} \\ &=& \frac{d^{n-2}}{dz^{n-2}} \frac{1}{2}\frac{-1}{2}(-4)^2(1-4z)^{\frac{-3}{2}} \\ &=& \frac{d^{n-3}}{dz^{n-3}} \frac{1}{2}\frac{-1}{2}\frac{-3}{2}(-4)^3(1-4z)^{\frac{-5}{2}} \\ &=& -\frac{\prod\limits_{p = 1}^{n - 1}{(2p - 1)}}{2^n}(4)^n (1-4z)^{\frac{1-2n}{2}} \\ &=& -\prod\limits_{p = 1}^{n - 1}{(2p - 1)}(2)^n (1-4z)^{\frac{1-2n}{2}} \end{eqnarray*} $

So the Taylor expansion around $ 0 $ would be given by:

$ \begin{eqnarray*} \sqrt{1-4z} &=& 1 + \sum\limits_{q = 1}^{\infty}{\frac{\frac{d^q}{dx^q}\sqrt{1-4z}|_{z=0} z^q}{q!}} \\ &=& 1 + \sum\limits_{q = 1}^{\infty}{\frac{-\prod\limits_{p = 1}^{q - 1}{(2p - 1)}(2)^q (1-4z)^{\frac{1-2q}{2}}|_{z=0} z^q}{q!}} \\ &=& 1 + \sum\limits_{q = 1}^{\infty}{\frac{-\prod\limits_{p = 1}^{q - 1}{(2p - 1)}(2)^q z^q}{q!}} \\ &=& 1 + \sum\limits_{q = 1}^{\infty}{\frac{-\prod\limits_{p = 1}^{q - 1}{(2p - 1)} (q-1)! (2)^q z^q}{(q-1)!q!}} \\ &=& 1 + \sum\limits_{q = 1}^{\infty}{\frac{-2(\prod\limits_{p = 1}^{2q - 2}{p}) z^q}{(q-1)!q!}} \\ &=& 1 + \sum\limits_{q = 1}^{\infty}{\frac{-2(2q - 2)! z^q}{(q-1)!q!}} \\ \end{eqnarray*} $

At this point it should be obvious for us that we should choose the answer with negative sign (so that all coefficients are positive), finally we reach

$ \begin{eqnarray*} C(z) &=& \frac{1 - \sqrt{1 - 4z}}{2z} \\ &=& \frac{1 - (1 + \sum\limits_{q = 1}^{\infty}{\frac{-2(2q - 2)! z^q}{(q-1)!q!}})}{2z} \\ &=& \frac{\sum\limits_{q = 1}^{\infty}{\frac{2(2q - 2)! z^q}{(q-1)!q!}}}{2z} \\ &=& \sum\limits_{q = 1}^{\infty}{\frac{2(2q - 2)! z^{q-1}}{2(q-1)!q!}} \\ &=& \sum\limits_{q = 1}^{\infty}{\frac{(2q - 2)! z^{q-1}}{(q-1)!(q-1)!q}} \\ &=& \sum\limits_{q = 0}^{\infty}{\frac{(2q)! z^{q}}{(q)!(q)!(q+1)}} \\ \end{eqnarray*} $

Phew! All these work just to get to the point $ C(n) = \left(\begin{array}{c}2q \\ q\end{array}\right)\frac{1}{n+1} $. To be honest, I knew the answer before I derived it. These numbers are known as the Catalan number and the solution for this problem is also well known. The above merely serve as an exercise for me to get my memory back on how it was derived.

While the calculation is extended, the code is, surprisingly, simple. Here it is:

Code:

#include "stdafx.h"

// https://leetcode.com/problems/unique-binary-search-trees/

#include "LEET_UNIQUE_BINARY_SEARCH_TREES.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_UNIQUE_BINARY_SEARCH_TREES
{
    class Solution
    {
    public:
        int numTrees(int n)
        {
            long long result = 1;
            int u = 2 * n;
            for (int v = 1; v <= n; v++, u--)
            {
                result *= u;
                result /= v;
            }
            return result / (n + 1);
        }
    };
};

using namespace _LEET_UNIQUE_BINARY_SEARCH_TREES;

int LEET_UNIQUE_BINARY_SEARCH_TREES()
{
    Solution solution;
    cout << solution.numTrees(19) << endl;
    return 0;
}

No comments :

Post a Comment