path_sum.py

class N:
    """Simple Binary Node class."""

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

    def __repr__(self):
        """Representation; useful for debugging tree."""
        lv = f" L={self.left.val}" if self.left else ""
        rv = f" R={self.right.val}" if self.right else ""
        return f"<N {self.val}{lv}{rv}>"


def path_sum(node, need):
    """Is there a node->leaf path summing up to `need`

    Make a simple tree:

    >>> root = N(5, N(4, N(11, N(7), N(2))), N(8, N(13), N(4, None, N(1))))

    Test winning path (5->4->11->2):

    >>> path_sum(root, 22)
    True

    Winning except that it doesn't reach leaf (5->4):

    >>> path_sum(root, 9)
    False
    """

    need -= node.val

    # print("path_sum after fixing need", node, need)

    # base case: we're a leaf node

    if not node.left and not node.right:
        return need == 0

    # non-base case: see if either L/R # child path (recursively) works

    if node.left and path_sum(node.left, need):
        return True

    if node.right and path_sum(node.right, need):
        return True

    return False