# ETOOBUSY ðŸš€ minimal blogging for the impatient

# PWC113 - Recreate Binary Tree

**TL;DR**

On with TASK #2 from the Perl Weekly Challenge #113. Enjoy!

# The challenge

You are given a Binary Tree.

Write a script to replace each node of the tree with the sum of all the remaining nodes.

ExampleInput Binary Tree

`1 / \ 2 3 / / \ 4 5 6 \ 7`

Output Binary Tree

`27 / \ 26 25 / / \ 24 23 22 \ 21`

# The questions

When in the past the challenge proposed a binary tree, I took it very literally to get the inputs from the ASCII art representation above. Iâ€™ll consider this as a solved problem and assume that the input is provided in a parsed form.

# The solution

Our algorithm will do two passes over the tree:

- in the first pass, we accumulate the values to end up with the overall sum $S$ of all nodes in the tree;
- in the second pass, we will substitute every value $v$ in every node
with $S - v$, i.e.
*the sum of all the remaining nodes*.

At this pointâ€¦ we only need the code:

```
#!/usr/bin/env perl
use 5.024;
use warnings;
use experimental qw< postderef signatures >;
no warnings qw< experimental::postderef experimental::signatures >;
sub recreate_binary_tree ($tree) {
my $sum = 0;
for my $cb (
sub ($n) { $sum += $n->{value} },
sub ($n) { $n->{value} = $sum - $n->{value} },
)
{
my @queue = ($tree);
while (@queue) {
my $node = shift(@queue) // next;
$cb->($node);
next unless exists $node->{children};
push @queue, $node->{children}->@*;
} ## end while (@queue)
} ## end for my $cb (sub ($n) { ...})
return $tree;
} ## end sub recreate_binary_tree ($tree)
sub node ($value, $left = undef, $right = undef) {
my %retval = (value => $value);
$retval{children} = [$left, $right]
if defined($left) || defined($right);
return \%retval;
} ## end sub node
sub printout ($root, $indent = 0) {
my $value = defined($root) ? $root->{value} : '';
say ' ' x $indent, "<$value>";
printout($_, $indent + 1) for $root->{children}->@*;
}
# 1
# / \
# 2 3
# / / \
# 4 5 6
# \
# 7
my $T =
node(1, node(2, node(4, undef, node(7))), node(3, node(5), node(6)));
printout(recreate_binary_tree($T));
```

Considering that we have to do the same visit in the tree by only
changing a little action (sum in the first pass, substitute in the
second pass), we loop over two little *callback functions* that
encapsulate the specifics of the actions at each pass, and reuse the
rest of the code in pure *merciless refactoring* spirit.

Stay safe everyone!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*