LC-0096 Medium LeetCode

96. Unique Binary Search Trees

Math Dynamic Programming Tree Binary Search Tree Binary Tree

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 62% Topics: Math, Dynamic Programming, Tree, Binary Search Tree, Binary Tree

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 1

        def combination(n, k):
            count = 1
            # C(n, k) = (n) / 1 * (n - 1) / 2 ... * (n - k + 1) / k
            for i in xrange(1, k + 1):
                count = count * (n - i + 1) / i
            return count

        return combination(2 * n, n) - combination(2 * n, n - 1)

# Time:  O(n^2)
# Space: O(n)
# DP solution.
class Solution2(object):
    # @return an integer
    def numTrees(self, n):
        counts = [1, 1]
        for i in xrange(2, n + 1):
            count = 0
            for j in xrange(i):
                count += counts[j] * counts[i - j - 1]
            counts.append(count)
        return counts[-1]

Solution from kamyu104/LeetCode-Solutions · MIT