Find the minimum path sum in a binary tree

Question

I am working on the problem of finding the minimum path sum in a binary tree, and printing the path. The path can be from the root node to any leaf node.

Here is my code in Python 2.7. I am looking for advice for bugs, performance improvement ideas or general code style advice.

One specific question is: I am using a list result to track minimal sum so far, because a simple integer in Python 2.7 is not reference type (I mean change the value of an integer in one function call, does not impact the value of same variable in another function). Are there any more elegant ways to track the minimal sum so far?

class TreeNode:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
    def min_path(self, sum_so_far, prefix, result, result_path):
        if self.left:
            prefix.append(self.value)
            self.left.min_path(sum_so_far + self.value, prefix, result, result_path)
            prefix.pop(-1)
        if self.right:
            prefix.append(self.value)
            self.right.min_path(sum_so_far + self.value, prefix, result, result_path)
            prefix.pop(-1)
        if not self.left and not self.right: # leaf node
            prefix.append(self.value)
            if sum_so_far + self.value < result[0]:
                result[0] = sum_so_far + self.value
                if len(result_path) > 0:
                    result_path.pop(0)
                result_path.append(prefix[:])
            prefix.pop(-1)
if __name__ == "__main__":
    root = TreeNode(1, TreeNode(2, TreeNode(-4, None, None), TreeNode(5, None, None)), TreeNode(3, TreeNode(6, None, None), TreeNode(-7, None, None)))
    result = [float('inf')]
    result_path = []
    root.min_path(0, [], result, result_path)
    print result, result_path

Answer 1

1. There's no docstring. What kind of thing is a TreeNode? What does the min_path method do? What should I pass for each of the parameters?

2. The code is written in Python 2.7, which is obsolescent (it gets bug fixes but no new features). We'll see later that this causes inconvenience because of the lack of the nonlocal statement. I suggest switching to Python 3.

3. The duplicated code for pushing and popping the prefix list, and updating sum_so_far, can be avoided, like this:

   def min_path(self, sum_so_far, prefix, result, result_path):
       prefix.append(self.value)
       sum_so_far += self.value
       if self.left:
           self.left.min_path(sum_so_far, prefix, result, result_path)
       if self.right:
           self.right.min_path(sum_so_far, prefix, result, result_path)
       if not self.left and not self.right: # leaf node
           if sum_so_far < result[0]:
               result[0] = sum_so_far
               if len(result_path) > 0:
                   result_path.pop(0)
               result_path.append(prefix[:])
       prefix.pop(-1)
   

4. The duplicated code for visiting the children can be avoided, like this:

   children = [c for c in (self.left, self.right) if c]
   if children:
       for child in children:
           child.min_path(sum_so_far, prefix, result, result_path)
   else: # leaf node
       # etc.
   

5. But a better approach would be to use a locally defined function, like this:

   def min_path(root):
       """Return list of values on the minimum path from root to a leaf."""
       min_path = []
       min_sum = [float('inf')]
       prefix = []
   
       def visit(node, sum_so_far):
           prefix.append(node.value)
           sum_so_far += node.value
           children = [c for c in (node.left, node.right) if c]
           if children:
               for child in children:
                   visit(child, sum_so_far)
           elif sum_so_far < min_sum[0]:
               min_sum[0] = sum_so_far
               min_path[:] = prefix[:]
           prefix.pop(-1)
   
       visit(root, 0)
       return min_path
   

   This still uses the trick of updating the first element of a list in order to update a result inside a possibly nested function call, but at least here the trick is hidden inside the implementation, and not exposed to the caller.

   (In Python 3, you could write nonlocal min_sum and so avoid the need for the trick.)

6. Alternatively, you could use the stack of iterators pattern. This avoids making recursive function calls, and so there's no difficulty in maintaining the running minimum.

   def min_path(root):
       """Return list of values on the minimum path from root to a leaf."""
       min_path = []
       min_sum = float('inf')
       current_path = [0]
       current_sum = 0
       stack = [iter([root])]
       while stack:
           for node in stack[-1]:
               current_path.append(node.value)
               current_sum += node.value
               children = [n for n in (node.left, node.right) if n]
               stack.append(iter(children))
               if not children and current_sum < min_sum:
                   min_sum = current_sum
                   min_path = current_path[1:]
               break
           else:
               current_sum -= current_path.pop()
               stack.pop()
       return min_path