python - How does this code work to find the Minimum Depth of Binary Tree? -

i see code https://leetcode.com/discuss/37282/simple-python-recursive-solution-bfs-o-n-80ms

and answer

given binary tree, find minimum depth.

the minimum depth number of nodes along shortest path root

node down nearest leaf node.

class solution:         # @param {treenode} root         # @return {integer}         def mindepth(self, root):             if not root:                 return 0              nodes = [(root, 1)]             while nodes:                 node, curdepth = nodes.pop(0)                 if node.left none , node.right none:                     return curdepth                 if node.left:                     nodes.append((node.left, curdepth + 1))                 if node.right:                     nodes.append((node.right, curdepth + 1)) 

so confusion is, if node 1 has node 2 , node 3 .left , .right children, stack [(node 2, somedepth), (node 3 somedepth)]. stack pop out last element of list, (node 3 somedepth) unpacked while node 2 ignored. in case node 2 has no child, while node 3 has, isn't wrong using node 3 subsequent iteration?

the point missing is

nodes.pop(0) 

pops 0th element.

so wrong here:

then stack pop out last element of list, then...

imagine binary tree:

            1           /    \         2        3      /   \     /   \     4     5   6      7  /   \      /   \   / 8     9    10   11 12 

here state space change as(for simplicity, nodes named content-numbers):

# before 1st iteration. nodes = [(1, 1)]  # 1st iteration. node, curdepth = 1, 1 nodes = [(2, 2), (3, 2)]  # 2nd iteration. node, curdepth = 2, 2 nodes = [(3, 2), (4, 3), (5, 3)]  # 3rd iteration. node, curdepth = 3, 2 nodes = [(4, 3), (5, 3), (6, 3), (7, 3)]  # 4th iteration. node, curdepth = 4, 3 nodes = [(5, 3), (6, 3), (7, 3), (8, 4), (9, 4)]  # 5th iteration. node, curdepth = 5, 3 # here if node.left none , node.right none becomes true , curdepth i.e. 3 returned. 

as can seen, nodes processed breadth(of tree) wise it's bfs.