Given a binary tree, find the maximum path sum

Question

This is a leetcode.com problem.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example: Given the below binary tree,

   1
  / \
 2   3 Return 6.

Following is my solution that is accepted.

1. As you can see I have used a magic number in place of -inf. This is not only inelegant, it will actually produce wrong answer if the input node has values in that range. I can think of a few ways to solve it, but I am open to suggestions about how you would do it. I can perhaps use special value like None but that introduces extra if logic that's not that beautiful. Are there better ideas?

2. Do you have suggestions for better names for variables and methods? Please ignore the name of class (and the fact that it does use class) since this is due to how Leetcode's wants it to be written.

To better understand the code, the intuition is, for any given subtree rooted at node n, I calculate the maximum path that includes n as one endpoint and ends within that subtree. I also calculate the maximum path that is between any two node in that subtree (to do that I take the max of few things). The global solution is then computed at the root of the whole tree.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxPathSum(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        _, max_path = self.max_path(root)
        return max_path

    def max_path(self, node):
        if node == None:
            return 0, -9999999

        max_path_from_left, max_path_in_left = self.max_path(node.left)
        max_path_from_right, max_path_in_right = self.max_path(node.right)

        max_path_from_current = max(\
            max_path_from_left + node.val,\
            node.val, \
            max_path_from_right + node.val)

        max_path = max(max_path_in_left, max_path_in_right, \
                  max_path_from_left + node.val + max_path_from_right, \
                  max_path_from_current)
        return max_path_from_current, max_path

Answer 1

1. If you want \$−∞\$, just write float('-inf').

2. The names could be improved by removing the common prefix max_path_, using to instead of from, and node instead of current. (The replacements are shorter than the originals, so reduce the size of the code without reducing readability.)

3. The computation of max_path_from_current (which becomes to_node after my renaming), can be simplified by pulling the addition of node.val out of the call to max:

   to_node = node.val + max(0, to_left, to_right)
   

4. Since max_path is only called from maxPathSum it makes sense for it to be a local function there. Then you could avoid the unnecessary use of self.

Revised code:

def maxPathSum(self, root):
    def max_path(node):
        if node is None:
            return 0, float('-inf')
        to_left, in_left = max_path(node.left)
        to_right, in_right = max_path(node.right)
        to_node = node.val + max(0, to_left, to_right)
        in_node = max(in_left, in_right, to_left + node.val + to_right, to_node)
        return to_node, in_node
    return max_path(root)[1]