# Should-be-6-Liner

• If only LeetCode had a `TreeNode(val, left, right)` constructor... sigh. Then I wouldn't need to provide my own and my solution would be six lines instead of eleven.

``````def generateTrees(self, n):
def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node
def trees(first, last):
return [node(root, left, right)
for root in range(first, last+1)
for left in trees(first, root-1)
for right in trees(root+1, last)] or [None]
return trees(1, n)
``````

Or even just four lines, if it's not forbidden to add an optional argument:

``````def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node

class Solution:
def generateTrees(self, last, first=1):
return [node(root, left, right)
for root in range(first, last+1)
for left in self.generateTrees(root-1, first)
for right in self.generateTrees(last, root+1)] or [None]
``````

Just another version, using loops instead of list comprehension:

``````def generateTrees(self, n):
def generate(first, last):
trees = []
for root in range(first, last+1):
for left in generate(first, root-1):
for right in generate(root+1, last):
node = TreeNode(root)
node.left = left
node.right = right
trees += node,
return trees or [None]
return generate(1, n)``````

• OMG, always learn a lot from your code! Plz keep posting! Really appreciate it!

• Love this concise code. Few people can their code clean and effective at the mean time.

• @1337c0d3r shouldn't we add the possibility to initialize left and right pointers in the TreeNode constructor? I was trying to do what Stefan was doing with list comprehension but got frustrated cause we can't do that.

• Can we ask Admin group to update the interface of TreeNode like this.

``````class TreeNode:
def __init__(self, x, left=None, right=None):
self.val = x
self.left = left
self.right = right
``````

• @StefanPochmann said in Should-be-6-Liner:

node,

Could you please explain what the comma indicates. Thank you.

• @zeusidkz A tuple.

• What is the time complexity?

• I think we should use copy.deepcopy to generate a new subtree for each new root for safety. But it can not pass the OJ ...

• @SamuraiLucifer said in Should-be-6-Liner:

But it can not pass the OJ ...

Why not?

• @StefanPochmann TLE at the last input, where n = 8

• @SamuraiLucifer The following easily gets accepted (in about 500-600 ms):

``````def generateTrees(self, n):
if n == 0: return []
def node(val, left, right):
node = TreeNode(val)
node.left = left
node.right = right
return node
def trees(first, last):
return [node(root, copy.deepcopy(left), right)
for root in range(first, last+1)
for left in trees(first, root-1)
for right in trees(root+1, last)] or [None]
return trees(1, n)``````

• @StefanPochmann Oh, yes, since we don't need to copy right children. Thanks !

• WOW!!!AMAZING!!!

• Why not add a cache?

``````class Solution(object):
def generateTrees(self, n):
if n < 1: return []
cache = {}
def generate(first, last):
if first > last: return [None]
if (first, last) in cache: return cache[first, last]
trees = []
for root in range(first, last+1):
for left in generate(first, root-1):
for right in generate(root+1, last):
node = TreeNode(root)
node.left = left
node.right = right
trees += node,
cache[first, last] = trees
return trees
return generate(1, n)
``````

• @FindRX said in Should-be-6-Liner:

Because I don't need to.

• @StefanPochmann
You mean the code without cache is more readable?
or the improvement is minor so it's not necessary?

• @FindRX I mean I don't need to add a cache because it's easily fast enough to be accepted without caching.

• @StefanPochmann