I am solving a question where we are asked to return the sum of the Depths of all the nodes in a Binary Tree.

For example:

Usually I would use a debugger to find the error in my code, but I don't know how to set up trees/binary tree in my IDE.

My code below passes most of the tests, but fails some. It fails the above test, and produces an output of 20 instead of 16.

def nodeDepths(root):
    queue = [root]
    sumOfDepths = 0
    currentDepth = 0
    while len(queue):
        for _ in range(len(queue)):
            currentNode = queue.pop()
            sumOfDepths  = currentDepth
            if currentNode.left:
                queue.append(currentNode.left)
            if currentNode.right:
                queue.append(currentNode.right)
        currentDepth  = 1

    return sumOfDepths

Any suggestions where the code fails/is doing something unexpected.

CodePudding user response：

I believe the source of your error is in your current_node = queue.pop() statement. According to the docs "The argument passed to the method is optional. If not passed, the default index -1 is passed as an argument (index of the last item)." Because you are pulling the last entry from the queue everything works okay until you have entries in the queue from different depths. To fix this problem use current_node = queue.pop(0), this will always pull the oldest entry from the queue.