#Leet Code# Unique Tree

 1 class Solution:
 2     # @return an integer
 3     def numTrees(self, n):
 4         if n == 0:
 5             return 0
 6         elif n == 1:
 7             return 1
 8         else:
 9             part_1 = self.numTrees(n-1) * 2
10             part_2 = 0
11 
12             for i in range(1,n-1):
13                 part_left = self.numTrees(i)
14                 part_right = self.numTrees(n - 1 - i)
15                 part_2 += part_left * part_right
16             
17             return part_1 + part_2