BFS list comprehension iterative option

Question

This BFS traversal uses a list comprehension to traverse a tree

def levelOrderBottom(self, root):
    res, queue = [], [root]
    while queue:
        res.append([node.val for node in queue if node])
        queue = [child for node in queue if node for child in (node.left, node.right)]
    return res[-2::-1]

For the

  res.append([node.val for node in queue if node])

I know that can be done iterative as

  for node in queue:
      if node:
          res.append([node.val])

but I can't quite wrap my head around what this code

  queue = [child for node in queue if node for child in (node.left, node.right)]

is doing iteratively, nor replicate it in a non list comprehension format

https://stackoverflow.com/questions/18072759/list-comprehension-on-a-nested-list — Chris_Rands, May 25 '19 at 18:00

score 1 · Accepted Answer · answered May 25 '19 at 18:00

Nested list comprehensions translate to nested for loops, in the same order.

queue = [child for node in queue if node for child in (node.left, node.right)]

becomes

queue = []
for node in queue:
    if not node:
        continue
    for child in (node.left, node.right):
        queue.append(child)

BFS list comprehension iterative option

1 Answers1