Unique Binary Search Trees

Problem: Unique Binary Search Trees

It seems quit easy to get that there are only 2 unique binary search trees for 2 elements. So what about 3 elements? There can be 3 ways to insert the 3rd element into the tree.

1. Insert as root, there are 2 options for the 3rd element to choose. Thus 2 results, as shown at the 2nd and 3rd position of the image.

2. Insert as leaf, there are also 2 options. Thus 2 results, too, as shown at the 4th and 5th position of the image.

3. Insert into the middle. It seems easy to get that the 3rd element can be inserted into the 2nd level with 1st element at root and 2nd element at leaf. As shown as the 1st result in the image.

To conclude, for n elements, to insert the last element into the tree with n-1 elements, we need to divide n-1 elements into 2 groups. One group with a elements and the other with b elements, where a + b = n - 1. One group abstracted as root tree of new element and the other abstracted as subtree. Due to the property of BST, elements must be divided due to their order. We will prove that later. Thus we calculate situations of different division and add them up to get the result.

Assume T(n) represents numbers of unique binary search trees for n elements. Due to our conclusion, we can write that:

$T(n) = T(0) * T(n-1) + T(1) * T(n-2) + ... + T(n-1) * T(0), T(0) = 1$

when n = 3:

$T(3) = T(0) * T(2) + T(1) * T(1) + T(2) * T(0)$

Code in python:

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = [1]
        for i in xrange(1, n+1):
            temp = 0
            for j in xrange(0, i):
                temp += res[j] * res[i-1-j]
            res.append(temp)
        return res[n]```

Proof, the last element must be the rightmost node. If we don't divide in order, there will be an element in 2nd group smaller than elements in first group as child of rightmost node, which confilts the definition of BST.