2

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.

jarmod
  • 71,565
  • 16
  • 115
  • 122
Jason T.
  • 113
  • 1
  • 2
  • 7

3 Answers3

2

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.

Bharel
  • 23,672
  • 5
  • 40
  • 80
  • Thank you. So I guess ```for i in q``` changes ```q``` whenever ```q``` changes along ```pop()``` and ```append()```, and it cause the unexpected results. – Jason T. May 06 '22 at 22:47
  • 1
    @JasonT. That is correct. The iterator (object the `for` loop gained by calling `iter(q)`) runs on the live list (`q`), and takes a new `i` every iteration by index. When you `pop()` you mess up the index, unlike `len(q)` which is evaluated only once at the start. – Bharel May 06 '22 at 22:51
1

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
Baobab
  • 155
  • 8
1

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)
notoriousjere
  • 153
  • 9