# 5-6 lines fast python solution (48 ms)

• `level` is a list of the nodes in the current level. Keep appending a list of the values of these nodes to `ans` and then updating `level` with all the nodes in the next level (kids) until it reaches an empty level. Python's list comprehension makes it easier to deal with many conditions in a concise manner.

Solution 1, (6 lines)
``````def levelOrder(self, root):
ans, level = [], [root]
while root and level:
ans.append([node.val for node in level])
LRpair = [(node.left, node.right) for node in level]
level = [leaf for LR in LRpair for leaf in LR if leaf]
return ans
``````

Solution 2, (5 lines), same idea but use only one list comprehension in while loop to get the next level
``````def levelOrder(self, root):
ans, level = [], [root]
while root and level:
ans.append([node.val for node in level])
level = [kid for n in level for kid in (n.left, n.right) if kid]
return ans
``````

Solution 3 (10 lines), just an expansion of solution 1&2 for better understanding.
``````def levelOrder(self, root):
if not root:
return []
ans, level = [], [root]
while level:
ans.append([node.val for node in level])
temp = []
for node in level:
temp.extend([node.left, node.right])
level = [leaf for leaf in temp if leaf]
return ans``````

• solution 1 is awesome! how would you combine lines 4 and 5 into one giant list comprehension?

• Added it to the post (solution 2). It's pretty straightforward but it would look longer. I changed the variable name to make it less than 80 characters in one line.

• Solution 2 is terrific.

• The Solution2 promotes the best understanding!

• Great solution:

I expanded it a little more for those who don't know list comprehension (such as myself :))

``````def levelOrder(self, root):
ret = []

level = [root]

while root and level:
currentNodes = []
nextLevel = []
for node in level:
currentNodes.append(node.val)
if node.left:
nextLevel.append(node.left)
if node.right:
nextLevel.append(node.right)
ret.append(currentNodes)
level = nextLevel

return ret``````

• thank you for sharing your solution.

• An alternative solution using the deque data structure. It is a list like object with O(1) appends and pops from both the left and right sides.

``````from collections import deque
def levelOrder(self, root):
# traverse in order level, keeping track of (row number, current node)
queue = deque([(0, root)])
# keep track of the nodes in each row
d = {}

while queue:
row, node = queue.popleft()
if node:
d[row] = d.get(row, []) + [node.val]
queue += (row+1, node.left), (row+1, node.right)

# return a list of lists containing node values in increasing order with respect to the row number
return [d[row] for row in sorted(d.keys())]``````

• @acmiyaguchi What would be space complexity of this solution?

• @gangofmumbai-gmail-com
We need to store each element of the tree in a hash-table keyed by the row, which requires `O(n)` space. A breadth first search requires worst case `O(2^d)` space for the queue where d is the depth of the tree. Since the total number of nodes in the tree will be greater than the nodes in a given level of a tree (`n >= 2^d`), this solution requires `O(n)` space for completion.

• @acmiyaguchi This is the kind of solution good for vertical order tree traversal.

• ``````[kid for n in level for kid in (n.left, n.right) if kid]
``````

Thanks for the explanation! I had a hard time figuring out how to flatten this listcomp.

I used sum(), but this is cleaner.

``````sum([[child in [node.left, node.right] if child] for node in nodes], [])
``````

I have confusion with the nested While-for-loop. And, does append within the loop count for extra time?

I will really appreciate your help. Thank you!

• Using lambda map reduce and filter:

``````def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root is None:
return []
curr, result = [root], []
while curr:
result.append(map(lambda x: x.val, curr))
curr = filter(lambda x: x is not None, reduce(lambda x, y: x + y, map(lambda x: [x.left, x.right], curr)))
return result``````

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