LC 0096 [M] Unique Binary Search Trees - ALawliet/algorithms GitHub Wiki

O(n^2) because if we had the numbers 1 2 3 4 5
we much consider each as the root node

class Solution:
    def numTrees(self, n: int) -> int:
        # numTree[4] = numTree[0] * numTree[3] +
        #      numTree[1] * numTree[2] +
        #      numTree[2] * numTree[1] +
        #      numTree[3] * numTree[1]
        numTree = [1] * (n + 1)
        
        # 0 nodes = 1 tree (empty tree)
        # 1 nodes = 1 tree (root node)
        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]

idea is to count at the root combinations = numTrees(number in left) * numTrees(number in right)

so it's a bottom-up solution so post-order/DP

class Solution:
    def numTrees(self, n: int) -> int:
        memo = {}
        
        def postorder(n):
          if n in memo:
            return memo[n]
          if n <= 1:
             return 1

          count = 0
          for i in range(1, n+1):
            countLeftSubtrees = postorder(i - 1)
            countRightSubtrees = postorder(n - i)
            count += (countLeftSubtrees * countRightSubtrees)

          memo[n] = count
          return count
        
        return postorder(n)