Binary Tree Path Sums

You could say that today’s date is a palindrome (02-02-2020). In light of the number of twos 👯‍♂️, I’ll be writing about a couple of binary tree problems (one today, another tomorrow).

Let’s get started on today’s problem.

From LeetCode:

You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Input:
"""
      10
     /  \ 
    5   -3
   / \    \ 
  3   2   11
 / \   \ 
3  -2   1
"""
8

Output:
3
# 1: 1 -> 5 -> 3
# 2: 5 -> 2 -> 1
# 3: -3 -> 11

If you’re wondering why this question’s been labelled as “Easy” on LeetCode, you’re definitely not alone! I’d consider a question of this sort to be of moderate difficulty.

Preliminary Considerations

This question is asking us to work with path sums, so we know that we’ll probably need to do:

• Run some standard tree traversal (DFS/BFS)
• Maintain some kind of accumulated state

If you jump into coding right away (a terrible idea), your first few lines might look something like this:

def traverse(subtree, curr_sum=0):
    nonlocal target_sum
    nonlocal res

    curr_sum += subtree.val
    if curr_sum == target_sum:
        # Increment the result

traverse(tree)

The above seems far from complete –– we know that any matching path doesn’t necessarily have to start from the root.

Our overarching approach will still be to analyse all paths from the tree’s root to its leaves, but in addition to accumulating the sum of the nodes along a path, we’ll also need maintain a pathsums hashmap to track the sums of subpaths (i.e. from the root to a non-leaf node):

# <sum of path>: <num of paths with this sum>
pathsums = collections.defaultdict(int)

Why do we track seen path sums? Storing binary tree path sums is useful in the same way that storing array prefix sums is.

Similarities to Array Prefix Sums

Array:       [5, 10, 15, 20]
Prefix Sums: [5, 15, 30, 50]

To find the sum of a subarray which starts from index i and ends at index j (inclusive), we take prefix_sums[j] and subtract prefix_sums[i-1] from it. Similarly, if we need to find a specific subarray whose sum equals a given value x, we can simply check if we’ve seen some prefix_sum[i] whose value is the same as prefix_sums[j] - x.

Each element in a numerical array is analogous to a node along a binary tree path. Suppose our target sum is 35:

"""
Tree Path: root -> subtree -> subtree -> leaf
Values:     5        10         15        20
Path Sums:  5        15         30        50
"""

• As we move down the tree and reach the leaf node, our curr_sum is raised to a value of 50.
• At this point, we would have stored entries for pathsums[5], pathsums[15], and pathsums[30].
• We can look up pathsums[50 - 35] (i.e. pathsums[15]) and conclude that a path summing to 35 must exist since we’ve seen pathsums for 50 and 15 along our current path.

Traversing the Tree

Let’s rewrite traverse() to match the logic we’ve described:

def traverse(subtree, curr_sum=0):
    nonlocal target_sum
    nonlocal res
 
    if not subtree:
        return

    curr_sum += subtree.val

    if curr_sum == target_sum:
        res += 1

    if curr_sum - target_sum in pathsums:
        # If a pathsum for curr_sum - target_sum
        # exists, then we know that a path which
        # sums to target_sum also exists
        res += pathsums[curr_sum - target_sum]

    pathsums[curr_sum] += 1

Notice that pathsums isn’t just a simple set of keys, it’s a mapping between path sums and their number of occurrences. We maintain counters for every possible path sum because the same path sum can technically occur multiple times:

"""
Tree Path: root -> subtree -> subtree -> subtree -> leaf
Values:     5         3          2          0        -2
Path Sums:  5         8         10         10         8
"""

In the above path, the path sums of 8 and 10 both occur twice.

Let’s flesh out the remainder of our traversal function. Specifically, we need to:

• Recurse on the lower levels of the tree
• Delete seen path sums as we backtrack, since they won’t apply to the next paths that we analyse

def traverse(subtree, curr_sum=0):
    nonlocal target_sum
    nonlocal res
 
    if not subtree:
        return

    curr_sum += subtree.val

    if curr_sum == target_sum:
        res += 1

    if curr_sum - target_sum in pathsums:
        res += pathsums[curr_sum - target_sum]

    pathsums[curr_sum] += 1

    traverse(subtree.left, curr_sum)
    traverse(subtree.right, curr_sum)

    pathsums[curr_sum] -= 1

Our traversal helper function is now complete. Applying it to the main algorithm is pretty straightforward:

def get_num_of_matching_paths(tree, target_sum):
    res = 0
    pathsums = collections.defaultdict(int)

    def traverse(subtree, curr_sum=0):
        # Update pathsums, recurse down the tree
        # ...

    traverse(tree)
    return res

Given n number of nodes, our algorithm runs in O(n) space and O(n) time.

With that, we’ve solved the Binary Tree Path Sums problem 🌲🧮.

Full Solution

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


def get_num_of_matching_paths(tree, target_sum):
    res = 0
    pathsums = collections.defaultdict(int)

    def traverse(subtree, curr_sum=0):
        nonlocal target_sum
        nonlocal res

        if not subtree:
            return

        curr_sum += subtree.val

        if curr_sum == target_sum:
            res += 1

        if curr_sum - target_sum in pathsums:
            res += pathsums[curr_sum-target_sum]

        pathsums[curr_sum] += 1

        traverse(subtree.left, curr_sum)
        traverse(subtree.right, curr_sum)

        pathsums[curr_sum] -= 1

    traverse(tree)
    return res