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

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.

CodePudding user response：

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.

CodePudding user response：

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

CodePudding user response：

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)