PWC 056 › Path Sum

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #2 this week is a simple tree traversal:

You are given a binary tree and a sum, write a script to find if the tree has a path such that adding up all the values along the path equals the given sum. Only complete paths (from root to leaf node) may be considered for a sum.

For both my Perl and Raku versions, I’m going super-lean with the implementation, using only array references. The “node,” which recursively defines an entire (sub)tree, looks like this:

• Element 0: Node’s value
• Elements 1..N: References to child nodes

Thus, the (Raku) syntax my @tree = [10, [18, [5], [2]], [8, [16, [18]], [9]]] describes a tree that looks like this:

              10
            /    \
           18     8
          / \    / \
         5   2  16  9
               /
              18

If we look for a path sum of 30, there is precisely one path with that sum: 10 → 18 → 2.

It’s worth noting that, although the task is limited to binary trees, my implementation will handle m-ary trees. Forcing it to handle only binary trees would actually be slightly more difficult, and a lot less useful.

Trees are inherently recursive data structures, so recursion is a natural tool for traversing them. In order to find a candidate path, I will start with the target $sum, and subtract the current node’s value from that $sum. The current @path will be maintained as well. There are two base cases:

1. The $sum is less than zero. This means we have overshot the target, and we can stop.
2. The $sum is equal to zero, and this node has no children (i.e., it’s a leaf node). This means we have found a target sum. We return that path.

The first base case is not strictly necessary; it’s an optimization. The second base case is where the solution is built and passed up the stack.

If none of those base cases trigger, then we simply call our function recursively on the current node, with the current sum, and path so far.

Perl

sub path_sum {
    my ($tree, $sum_left, @path) = @_;
    my ($val, @kids) = @$tree;
    push @path, $val;
    $sum_left -= $val;
    return [@path] if $sum_left == 0 and !@kids;
    return         if $sum_left <  0;

    map { path_sum($_, $sum_left, @path) } @kids;
}

Raku

#| Does a certain complete sum exist in the tree?
sub path-sum( @tree, $sum is copy, @path is copy = [] ) {
    my ($val, @kids) = @tree;
    @path.push: $val;
    $sum -= $val;

    return @path if $sum == 0 and !@kids;
    return Empty if $sum <  0;

    |@kids.map: { path-sum($_, $sum, @path) };
}

The Raku code highlights a couple of interesting differences in the languages.

is copy

First, the is copy is used here, so that I can freely munge the values without modifying the underlying variables. I do this for convenience in the case of $sum, but it’s more or less necessary for @path, at least without significant changes to the implementation.

List/Array flattening

Perl flattens lists, but does not flatten array refs. Perl also returns an empty list by default, which means a bare return just gets ignored in typical recursive subs like this. That made it easy to build a list of lists in the Perl version: I only had to put [ @path ] in square brackets to create an array ref.

In the Raku version, if I do not flatten anything, and do not return Empty, this is what path-sum returns for the sample tree in the code:

((() ([6 5 4 15])) ((Nil) (Nil)) (([6 1 16 7]))) # Wrong

We can see the desired results, [6 5 4 15] and [6 1 16 7], but all of those extra parentheses and Nils are undesirable byproducts of returning early from our base cases and operating on empty lists. We can flatten the results with the | prefix operator:

|@kids.map: { path-sum($_, $sum, @path) }

But that only gets us part-way there:

([6 5 4 15] Nil Nil [6 1 16 7]) # Still wrong

Raku returns Nil by default, which we could deal with by, say, using grep, but it’s far easier to explicitly return Empty in that one base case that is causing problems:

return Empty  if $sum < 0; # Without Empty, returns Nil

Of course that line could be removed, as it is only a (premature!) optimization, but it’s one of those premature optimizations that, at least for me, requires near-enough zero effort to implement and test that it’s worth it in the name of good code.

Efficiency

Hopefully it’s self-evident that the efficiency of these algorithms is O(n) on the number of nodes in the tree, as the recursive traversal looks at each node at most once.

Closing Thoughts

Calculating the sum and returning matching paths makes this a subset of a straightforward depth-first tree traversal.

This task was fairly straightforward, but then again, I only took a narrow slice of it. There are many ways I could have gone, and I’m excited to see what the other participants came up with.