2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$
  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
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.