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