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

Question

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_max_path_in_right_subtree,
 val_of_max_path_that_has_a_turning_point_at_root )
 return ( val_of_max_path_from_a_leaf_up_to_root,
 val_of_max_path_in_this_subtree )

Comments

I use very long descriptive variable names. I am not sure if I am overdoing it or not. Do you see a way to shorten them whilst maintaining meaning? I have an upcoming technical interview so I want to make sure I exhibit good style. Also, I will be coding in a shared Google Doc, so I won't have access to syntax highlighting. Any tips or suggestions are greatly appreciated.

• kfx: Yes, those names are too long. They contain some redundant information - that's one sign how to tell whether they're too long, rather than just long. For example, the "val" prefix does not tell anything new - sure it's a value, what else? Renaming val_of_max_path_that_has_a_turning_point_at_root -> max_path_through_root leaves all the important information intact.
• josfervi: @kfx My thought was that val_of_ helps distinguish between the value of a path and the path itself, but as you said that may be too much info. Would using a shorter vairable name and a comment to explain the meaning be a good compromise?
• Heslacher: I have rolled back the last edit. Please see what you may and may not do after receiving answers .

Answer 1

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

• Graipher: I would suggest using right_max and left_max for max_path_in_right_subtree and max_path_in_left_subtree. Can't think of anything good for max_path_from_a_leaf_up_to_root, though.
• Graipher: Maybe right_max_depth and right_max_path?