Best way to store the sum of all node depths?

Question

To sum up all the nodes' depths in any given binary tree, I've written the following recursive algorithm:

def nodeDepths(root):
    final=[0]
    helper(root,0, final)
    return final[0]

def helper(node,d, final):
    if not node:
        return 
    final[0]+= d
    helper(node.left,d+1, final)
    helper(node.right,d+1, final)

class BinaryTree:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

My thinking was: as I see each node, add the depth of that node to the final sum, then recursively call on the left and right with final list as an argument. At the end of the recursive call stack, final[0] should have the right value.

Is there a better way to do this? I have concerns about thread safety in general with global variables but is it a better practice to use global variables in this case?

Answer 1

PEP8

nodeDepths should be node_depths in snake_case.

Function naming

helper is not a helpful name for a function. If I were to guess what this does, it should maybe be called recurse_node_depths.

Instance methods

As it stands, BinaryTree does not deserve to have an __init__. It would be better-suited as a @dataclass or maybe a named tuple. That said, it probably makes more sense for node_depths to be an instance method where self replaces root.

Integer-by-reference

My first read of this code was wrong. final is only ever going to have one member. My guess is that you did this to effectively pass an integer by reference, but this is a gross hack. Instead, just return the evolving sum as an integer from your recursion, and the uppermost return will be the total that you need.

Slots

Another way to squeeze performance out of this is to initialize __slots__ for BinaryTree based on the three known members.

Recursion

Recursion is not a great idea in Python, for at least two reasons:

• Given that there is no indication to the maximum depth of your input tree, you may blow the stack.
• Since Python does not have tail recursion optimization, recursion is slower than some other languages.

So you should attempt to reframe this as an iterative implementation.