Given a binary tree, \$T\$ whose nodes have positive values, find the value of the maximal path

Problem

Problem is Maximum sum path from https://firecode.io

Given a binary tree, \$T\$, whose nodes have positive values find the value of a maximal path. A path is a simple path from a node to another node. The value of a path \$P\$ is

$$val(P) = \sum\limits_{u \in P} val(u)$$

that is, the sum of the values of the nodes along \$P\$. A maximal path \$M\$ is one that satisfies:

$$\forall\ \ paths\ \ P,\ \ val(P) \le val(M)$$

Python solution

```
class BinaryTreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right

class BinaryTree:
def __init__(self, root = None):
self.root = root

def max_sum_path(self, root):

_, val_of_max_path = self._val_of_max_path(root)

return val_of_max_path

def _val_of_max_path(self, root):
''' Returns a tuple:
( val of the maximal path
from a leaf up to root,

val of the maximal path
from a node to another
node in this subtree )
'''

# base case
if not root:
return (0, 0)

# recursive case

( val_of_max_path_from_a_leaf_up_to_left_child,
val_of_max_path_in_left_subtree ) = (

self._val_of_max_path(root.left) )

( val_of_max_path_from_a_leaf_up_to_right_child,
val_of_max_path_in_right_subtree ) = (

self._val_of_max_path(root.right) )

val_of_max_path_from_a_leaf_up_to_root = root.data + max(

val_of_max_path_from_a_leaf_up_to_left_child,
val_of_max_path_from_a_leaf_up_to_right_child )

val_of_max_path_that_has_a_turning_point_at_root = (

val_of_max_path_from_a_leaf_up_to_left_child +
root.data +
val_of_max_path_from_a_leaf_up_to_right_child )

val_of_max_path_in_this_subtree = max(

val_of_max_path_in_left_subtree,
val_of_m

The combination of the very long variable names and trying to follow the PEP8 "79 chars per line" rule really makes the code unreadable.

First of all, you can absolutely increase the allowed line length from 79 to a more practical 100 or 120. After all, we are writing code for humans to read, not machines.

Also, I think you can shorten the variable names by removing the "val_of_" part from the beginning. You don't lose any information by doing that.

Some other notes:

• you can define tuples without extra parenthesis, e.g. return 0, 0 instead of return (0, 0)

• the docstrings should be put in triple double-quotes. If a docstring is located on multiple lines, it should star with a new line (PEP8 reference)

Here is the code after applying the proposed changes:

class BinaryTree:
    def __init__(self, root=None):
        self.root = root

    def max_sum_path(self, root):
        _, max_path = self._max_path(root)
        return max_path

    def _max_path(self, root):
        """
        Returns a tuple:
            (val of the maximal path from a leaf up to root,
             val of the maximal path from a node to another node in this subtree).
        """

        # base case
        if not root:
            return 0, 0

        # recursive case
        max_path_from_a_leaf_up_to_left_child, max_path_in_left_subtree = self._max_path(root.left)
        max_path_from_a_leaf_up_to_right_child, max_path_in_right_subtree = self._max_path(root.right)

        max_path_from_a_leaf_up_to_root = root.data + max(max_path_from_a_leaf_up_to_left_child, 
                                                          max_path_from_a_leaf_up_to_right_child)

        max_path_that_has_a_turning_point_at_root = max_path_from_a_leaf_up_to_left_child + \
                                                    root.data + \
                                                    max_path_from_a_leaf_up_to_right_child
        max_path_in_this_subtree = max(max_path_in_left_subtree, 
                                       max_path_in_right_subtree,
                                       max_path_that_has_a_turning_point_at_root)

        return max_path_from_a_leaf_up_to_root, max_path_in_this_subtree

StackExchange Code Review Q#159165, answer score: 3