# 2 solutions, recursion, and with caching

• caching here does not improve the big O complexity, but it will improve runtime cause of reduced recursive calls.

brute force recursion:

``````class Solution(object):
def gen_trees_util(self, start, end):
if start > end:
return [None]

trees = []
for root in xrange(start, end + 1):
for l_subtree in self.gen_trees_util(start, root-1):
for r_subtree in self.gen_trees_util(root+1, end):
curr_root = TreeNode(root)
curr_root.left = l_subtree
curr_root.right = r_subtree
trees.append(curr_root)

return trees

def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n < 1:
return []
return self.gen_trees_util(1, n)
``````

with caching:

``````class Solution(object):
def gen_trees_util(self, start, end, tree_cache):
if start > end:
return [None]

if len(tree_cache[start][end]) > 0:
return tree_cache[start][end]

for root in xrange(start, end + 1):
for l_subtree in self.gen_trees_util(start, root-1, tree_cache):
for r_subtree in self.gen_trees_util(root+1, end, tree_cache):
curr_root = TreeNode(root)
curr_root.left = l_subtree
curr_root.right = r_subtree
tree_cache[start][end].append(curr_root)

return tree_cache[start][end]

def generateTrees(self, n):
"""
:type n: int
:rtype: List[TreeNode]
"""
if n < 1:
return []

tree_cache = [[[] for j in xrange(n+1)] for i in xrange(n+1)]
return self.gen_trees_util(1, n, tree_cache)``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.