Leetcode 96: Unique Binary Search Trees

https://leetcode.com/problems/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

 

Code

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if not n:
            return 0
            
        numOfTrees = [0] * (n+1)     # for easier indexing. Using numOfTrees[1:]
        numOfTrees[0] = 1
        
        for i in xrange(1, n+1):
            for j in xrange(1, i+1):
                numOfTrees[i] += numOfTrees[j-1] * numOfTrees[i-j] 
            
        return numOfTrees[n]

 

Idea

When you are given `n` (`n` is the size of sorted numbers to be placed in BST), there are multiple ways to construct unique BSTs depending on which element is placed as the root: you can put the first element as the root, then place the remaining `n-1` elements in the right tree. You can put the second element as the root, then place the first element as the left tree and the remaining `n-2` elements in the right tree. So on and so forth. 

Therefore, you can use an array, `numOfTrees` in my code, to store the number of unique BSTs. The final result, `numOfTrees[n]`, will be based on `numOfTrees[n’]` where `n’ < n`: You can put 1~n as root. When you put element `i` (`1<=i<=n`) as the root, its left tree can have `numOfTrees[i-1]` different unique ways of construction and its right tree can have `numOfTrees[n-i]` ways of construction. So the total number of unique trees when root equal to `i` is `numOfTrees[i-1] *numOfTrees[n-i]`.

A more mathematical way is to directly solve this problem using Catalan Number. Then you only need O(N) time and O(1) space. Please find introduction to Catalan Number below:

catalan