Python deque and popleft (part of collections module)

Question

This gives a list containing the path of every root to leaf:

def binaryTreePaths(self, root):
    from collections import deque
    if root is None:
        return []
    queue = deque( [ [root, str(root.val)] ] )
    ans = []
    while queue:
        front, path = queue.popleft()
        if front.left is None and front.right is None:
            ans += path,
            continue
        if front.left:
            queue += [front.left, path + "->" + str(front.left.val)],
        if front.right:
            queue += [front.right, path + "->" + str(front.right.val)],
    return ans

I don't understand how this works because say we have a tree that's 1-2-3 (node 1 has both left and right child). At the first line after the while loop, when you popleft it, queue is deque ([ ]) again. Since front is node1 and front.left exists (since node1 has a left child), we append front.left, and a string to the queue again.

So then the queue is deque([node2, "stringhere"]). Then we hit the third if statement: since node1 does have a right child (node3), we add to queue again so then queue becomes deque([node2, "stringhere", node3, "anotherstring"]).

Then we go back and hit the while loop; since queue is not empty, we have:

front, path = queue.popleft()

where our queue is deque([node2, "stringhere", ndoe3, "anotherstring"]) but it's not possible to call front, path on this because there are 4 arguments in the queue.

What am I not getting?

Answer 1

You are missing the , at the end of the line, which makes the item being added to the queue a tuple.

The normal way is to use the append method

    if front.left:
        queue.append([front.left, path + "->" + str(front.left.val)])
    if front.right:
        queue.append([front.right, path + "->" + str(front.right.val)])

For bonus points, use str.format too

    if front.left:
        queue.append([front.left, "{}->{}".format(path, front.left.val)])
    if front.right:
        queue.append([front.right, "{}->{}".format(path, front.right.val)])

and remove the duplication of code in the appending

    for node in (front.left, front.right):
        if node:
            queue.append([node, "{}->{}".format(path, node.val)])