e4c

class BTNode(object):
    """A node in a binary tree."""

    def __init__(self, item, left=None, right=None):
        """(BTNode, object, BTNode, BTNode) -> NoneType
        Initialize this node to store item and have children left and right,
        as well as depth 0.
        """
        self.item = item
        self.left = left
        self.right = right
        self.depth = 0  # the depth of this node in a tree

    def __str__(self):
        """(BTNode) -> str
        Return a "sideways" representation of the subtree rooted at thisnode,
        with right subtrees above parents above left subtrees and each node on
        its own line, preceded by as many TAB characters as the node's depth.
        """
        # If there is a right subtree, add an extra TAB character in front of
        # every node in its string representation, with an extra newline at the
        # end (ready to be concatenated with self.item).
        if self.right:
            str_right = "\t" + str(self.right).replace("\n", "\n\t") + "\n"
        else:
            str_right = ""
            # The string representation of self.item: if item is a string, use
            # repr(item) so that quotes are included and special characters are
            # treated correctly -- just like in a list; else use str(item).
        if isinstance(self.item, str):
            str_item = repr(self.item)
        else:
            str_item = str(self.item)
            # If there is a left subtree, add an extra TAB character in front of
            # every node in its string representation, with an extra newline at the
            # beginning (ready to be concatenated with self.item).
        if self.left:
            str_left = "\n\t" + str(self.left).replace("\n", "\n\t")
        else:
            str_left = ""
        # Put the right subtree above the root above the left subtree.
        return str_right + str_item + str_left

    def sum_to_deepest(self):
        """(BTNode) -> int
        Return the sum of the keys on a deepest path from this node to a
        leaf. Return the maximum sum if many leaves have the same depth.
        """
        return self._depth_and_sum(0, 0)[1]

    def _depth_and_sum(self, self_depth, sum_so_far):
        #self_depth is the depth of this node. sum_so_far is the sum of
        #items above this node. Return a tuple of: the depth of the
        #deepest leaf in this node's subtree, and the sum of items down
        #to that node.
        if self.left is None and self.right is None:
            return self_depth, sum_so_far + self.item
        elif self.left is None:
            return self.right._depth_and_sum(self_depth + 1,
                                             sum_so_far + self.item)
        elif self.right is None:
            return self.left._depth_and_sum(self_depth + 1,
                                            sum_so_far + self.item)
        else:
            #When comparing tuples, max will first look at the first
            #element (the depth), and then the second (the sum). Thus it
            #will return the largest of all sums to elements tied for
            #deepest.
            return max(self.left._depth_and_sum(self_depth + 1,
                                                sum_so_far + self.item),
                       self.right._depth_and_sum(self_depth + 1,
                                                 sum_so_far + self.item))