96. Unique Binary Search Trees - Explanation

1. Recursion

class Solution:
    def numTrees(self, n: int) -> int:
        if n <= 1:
            return 1

        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)
        return res

Time & Space Complexity

Time complexity: $O(3 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:

    def __init__(self):
        self.dp = {}

    def numTrees(self, n: int) -> int:
        if n <= 1:
            return 1
        if n in self.dp:
            return self.dp[n]

        res = 0
        for i in range(1, n + 1):
            res += self.numTrees(i - 1) * self.numTrees(n - i)

        self.dp[n] = res
        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

3. Dynamic Programming (Bottom-Up)

class Solution:
    def numTrees(self, n: int) -> int:
        numTree = [1] * (n + 1)

        for nodes in range(2, n + 1):
            total = 0
            for root in range(1, nodes + 1):
                left = root - 1
                right = nodes - root
                total += numTree[left] * numTree[right]
            numTree[nodes] = total

        return numTree[n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

4. Catalan Numbers - I

class Solution:
    def numTrees(self, n: int) -> int:
        res = 1
        for i in range(1, n):
            res *= (n + i + 1)
            res //= i
        return res // n

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

5. Catalan Numbers - II

class Solution:
    def numTrees(self, n: int) -> int:
        res = 1
        for i in range(n):
            res *= (4 * i + 2) / (i + 2)
        return int(res)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.