5
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – kfx Mar 28 '17 at 18:50
  • \$\begingroup\$ @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? \$\endgroup\$ – josfervi Mar 29 '17 at 0:39
  • 1
    \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Mar 29 '17 at 4:44
3
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – Graipher Mar 28 '17 at 19:06
  • 2
    \$\begingroup\$ Maybe right_max_depth and right_max_path? \$\endgroup\$ – Graipher Mar 28 '17 at 19:09

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.