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.

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