class Solution:
  def countTrees(self, n):
    
    def solve(start, end):
      if start > end:
        return 1
        
      count = 0 
      
      for i in range(start, end + 1):
        lefts = solve(start, i - 1)
        rights = solve(i + 1, end)

        count += lefts * rights
      
      return count

    return solve(1, n)