*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.

Continue reading “PWC 056 › Path Sum”