# Python BFS

• ``````def findValueMostElement(self, root):
maxes = []
row = [root]
while any(row):
maxes.append(max(node.val for node in row))
row = [kid for node in row for kid in (node.left, node.right) if kid]
return maxes``````

• @StefanPochmann
`Any` to deal will the case [None] is brilliant.
Could give some explanation on the code:

``````[kid for node in row for kid in (node.left, node.right) if kid]
``````

I have never used two `for` embedded.

• @lee215 I'll try to explain this part. Please tell me if I'm wrong.

``````row = [kid for node in row for kid in (node.left, node.right) if kid]
``````

is equal to:

``````row = [a,b,c,d...]
xxx = []
for node in row:
for kid in (node.left, node.right):
if kid:
xxx += kid,
row = xxx
``````

Note that @StefanPochmann keep updates the row list again and again. How great this is!

• excellent and elegant

• Hi Stefan,
Thank you for a nice solution.
I am always surprised how you write the most concise solution.
Thank you.

• @StefanPochmann Just curious, is the max in "max(node.val for node in row)" taking the max at each sequential step or is it taking the max after the for loop is completed? Given that you don't need that extra for loop for calculating the max since you already go through each node in the row in the other for loop.

• @livelearn said in Python BFS:

taking the max after the for loop is completed

Not sure what you mean with that...

• @StefanPochmann For example, is it doing this:

``````maxx=inf("-inf")
for i in a:
maxx=max(i,maxx)
or
for i in a
tmp.append(i)
max(tmp)``````

• @livelearn It's neither of those. It looks more like your second version, as I call `max` just once and I do give it only one thing. But it really is more like your first version. That one thing I give to `max` is a generator, which provides the values one by one on demand. And then `max` will, under the hood, do something like your first version.

• @StefanPochmann Such condensed code, brilliant. The max per row and the row can be computed in the same pass to make the solution even quicker. I used the same BFS idea but computed max per row and rows in same pass.

Here's my solution: https://discuss.leetcode.com/topic/92079/simple-python-bfs-beats-99-83-65ms

• @pramttl said in Python BFS:

to make the solution even quicker

Doesn't look quicker to me. Where are your statistics?

I did some myself now, renaming our function and adding this one:

``````def largestValues(self, root):
for _ in range(100):
``````

Then I alternately submitted our solutions three times. The times (in ms):

``````mine yours
705   736
696   779
815   802
``````

They look very similar, with mine looking a bit quicker. I doubt you tested this properly or at all.

• @StefanPochmann In your solution there are 2 passes over the row, one to compute maximum and one to compute kids. Logically, wouldn't it be quicker to use a single pass to compute max and child row ?

I got 65 ms on Leetcode on submitting my solution (shared snapshot in comments section of my solution) and that's why I claimed it is quicker. Being new to Leetcode, wasn't aware that the runtime can vary so much on multiple submissions. (probably because of smaller test cases). I just wanted to highlight that single pass to compute row max and next row could be quicker if the tree is very large with several elements per row. If I am wrong, let me know ?

• @pramttl Your single pass does more than each of my two passes. It does the same as both of mine together. Granted, the pure iteration is done twice in mine, but yours spends more time on each item. You're calling `max` for each node (I only call it once per row) and you look up and call `curr_level_nodes.append` for each node. List comprehensions do that more efficiently. Compare what happens in each iteration in loop+append vs list comprehension:

``````>>> def f():
ans = []
for x in X:
ans.append(x)
return ans

>>> import dis
>>> dis.dis(f)
3           0 BUILD_LIST               0
3 STORE_FAST               0 (ans)

4           6 SETUP_LOOP              27 (to 36)
12 GET_ITER
>>   13 FOR_ITER                19 (to 35)
16 STORE_FAST               1 (x)

28 CALL_FUNCTION            1
31 POP_TOP
32 JUMP_ABSOLUTE           13
>>   35 POP_BLOCK

6     >>   36 LOAD_FAST                0 (ans)
39 RETURN_VALUE
>>> def g():
return [x for x in X]

>>> dis.dis(g)
3           0 BUILD_LIST               0
6 GET_ITER
>>    7 FOR_ITER                12 (to 22)
10 STORE_FAST               0 (x)