'Why "for i in q" makes the result different from "for i in range(len(q))"?

I have code for calculating max depth using BFS, which works fine, but I couldn't figure out why it fails if I replaced for i in range(len(q)): with for i in q:.

The code below works correctly and passes all tests:

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        
        q = list([root])
        level = 0
        while q:
            for i in range(len(q)):
                node = q.pop(0)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return level

But the code below with for i in q fails some tests:

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        
        q = list([root])
        level = 0
        while q:
            for i in q:                     # the only difference
                node = q.pop(0)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return level

for i in range(len(q)): and for i in q: provide exactly the same number of iterations or do I misunderstand something? I don't understand why it would make any difference... Any ideas?

Thank you.

pythonfor-loopbreadth-first-search


Solution 1:[1]

for i in range(len(q)): and for i in q: are not equivalent.

You modify q by popping and appending. When you modify a list during iteration, the internal iterator's behavior is undefined (usually skips stuff).

range(len(q)) checks q's length only once at the start, and from then on the iteration is defined.

Solution 2:[2]

It's because the q.pop(0) instruction also plays with q which makes your iteration shorter (see https://stackoverflow.com/a/13939416/10115198 for a detailed illustration).

It actually doesn't give the same amount of iterations! To get an idea of the problem:

q = [1, 2, 3]
for i in q:
    node = q.pop(0)
    print(i, node)

gives

1 1
3 2

but

q = [1, 2, 3]
for i in range(len(q)):
    node = q.pop(0)
    print(i, node)

gives

0 1
1 2
2 3

Solution 3:[3]

The key difference is that for i in range(len(q)) creates a new iterator (range) object from q at the time just before the loop. for i in q loops over items in q. Your issue is that you are actually modifying q from inside your loop with q.append(...) and q.pop(...), which can have unexpected behavior as you are seeing.

Simple example -- this will loop forever:

l = [1, 2, 3]
for i in l:
    print(i)
    l.append(999)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Bharel
Solution 2 Baobab
Solution 3 notoriousjere

Related Questions