This post is part of a series on Mohammad Anwar’s excellent Perl Weekly Challenge, where Perl and Raku hackers submit solutions 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, , ], [8, [16, ], ]] 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”