Raku Solutions Weekly Review
Tree Inversion
This is derived in part from my blog post made in answer to the Week 57 of the Perl Weekly Challenge organized by Mohammad S. Anwar as well as answers made by others to the same challenge.
The challenge reads as follows:
You are given a full binary tree of any height, similar to the one below:
1
/ \
2 3
/ \ / \
4 5 6 7
Write a script to invert the tree, by mirroring the children of every node, from left to right. The expected output from the tree above would be:
1
/ \
3 2
/ \ / \
7 6 5 4
The input can be any sensible machinereadable binary tree format of your choosing, and the output should be the same format.
Bonus: In addition to the above, you may wish to prettyprint your binary tree in a human readable textbased format as above.
I’ll definitely take the bonus, because making auxiliary subroutines to represent graphically the trees is the best way to check that inversion subroutine works correctly (or to easily detect the errors, if any). But I will not represent the tree edges (the /
and \
connecting vertically the letters), because it becomes a bit difficult with 4 levels and more or less unmanageable (and quite ugly) when there are more that 4 levels (well, Colin Crain found a nice solution presented below). For example, I chose to represent a 5level binary tree as follows:
1
2 3
4 5 6 7
8 9 a b c d e f
g h i j k l m n o p q r s t u v
I decided to implement two different subroutines for the display: one bft
(breadthfirst traversal) subroutine to construct an intermediate array of arrays in which each level of the tree is contained in one subarray:
[[1] [2 3] [4 5 6 7] [8 9 a b c d e f] [g h i j k l m n o p q r s t u v]]
and one display
subroutine to produce the graphical ASCII representation. The main reason for doing that is that the display
subroutine can thus be reused, independently of the internal tree representation.
Using an Array of Arrays
I have discussed in a recent blog post 3 different ways to represent a binary tree: hash of hashes, array of arrays and a simple flat array.
I have shown in that post and also there how to represent a binary tree with a nested array of arrays.
As an alternative, we might implement an array of arrays in which each of the subarrays contain one level of the tree, i.e. a breadthfirst representation of the tree. The tree of the task description might look like this:
[ [1], [2, 3], [4, 5, 6, 7] ]
With such an implementation, inverting the tree can be done in a simple oneliner:
$ perl6 e '([1], [2, 3], [4, 5, 6, 7]).map({[ .reverse ]}).say;'
([1] [3 2] [7 6 5 4])
or possibly even:
$ perl6 e '( (1), (2, 3), (4, 5, 6, 7) )>>.reverse.say;'
((1) (3 2) (7 6 5 4))
Note that this representation of a tree makes it possible to use directly the display
subroutine briefly described above, since it already has the breadthfirst format otherwise produced by the bft
subroutine.
However, we will detail here the two other solutions, using a flat array or a hash of hashes.
Using a Flat Array
We’ll start with a flat array. Binary trees can be stored in breadthfirst order as an array with an implicit data structure. This is similar to what is commonly done for binary heaps (i.e. a binary tree that keeps a partial order). Here, we’re not interested with partial order, but the idea is to use an array with the following properties. The item with subscript 0 is the value of the root node. The index of an element is used to compute the index of its parent and the indices of its children. The basic idea is that, for any node, the index of its parent is about half the index of the current node, and, conversely, the indices of the children are about twice the index of the current node. More precisely, for a tree starting at index 0, the exact formulas for a node with index $n
are commonly as follows:
 parent:
int( ($n1)/2 )
 left child:
2*$n + 1
 right child:
2*$n + 2
The root node is at index 0, and its children are at positions 1 and 2. The children of item with index 1 are at positions 3 and 4 and the children of 2 are at positions 5 and 6.
These rules may seem a bit complicated (and it is a bit tedious to compute these things manually), but they’re in fact quite easy to implement in a program:
sub children (Int $i) { 2*$i+1, 2*$i+2 }
sub parent (Int $i) { ($i1)/2; }
The parent
subroutine is provided here for the purpose of completeness, it will not be needed in our program.
Note that it is very easy to populate the binaryheaplike array from a graphical representation: you just need to perform a breadthfirst traversal, and provide empty slots (undefined values) for missing nodes, but that’s not necessary here, since we are told that we are only dealing with full binary trees. For example, this binary tree:
1
/ \
2 3
/ \ / \
4 5 6 7
can be encoded as:
my $tree = [1, 2, 3, 4, 5, 6, 7];
or even:
my $tree = [1 .. 7];
With this flat array representation, the invert
subroutine can be very simple (and needs not be recursive, since the data structure is not nested): we just use the bft
subroutine to get an array of arrays by level, reverse the components and flatten the overall structure:
sub invert ($tree) {
return [ map {  reverse @$_ }, bft($tree) ];
}
This is the complete code for this program:
use v6;
sub children (Int $i) { 2*$i+1, 2*$i+2 }
sub parent (Int $i) { ($i1)/2; } # not needed here
sub display ($tree) {
my @bft_tree = bft($tree);
my $start = (@bft_tree[*1]).elems;
my $sep_val = (2 * $start)  1;
for @bft_tree > @line {
my $sep = " " x $sep_val;
say " " x $start, join $sep, @line;
$start /= 2;
$sep_val = ($sep_val  1) / 2;
}
}
sub bft ($tree) { # Breadth First Traversal
my ($index, $level) = (0, 0);
my @bft_tree;
while ($index <= $tree.end) {
my $new_index = $index + 2 ** $level  1;
(@bft_tree[$level++]).append($tree[$index .. $new_index]);
$index = $new_index + 1;
}
return @bft_tree;
}
sub invert ($tree) {
return [ map {  reverse @$_ }, bft($tree) ];
}
my $tree = (1..9, 'a'..'v').flat;
say $tree;
say "\nTree before inversion";
display $tree;
my $inverted_tree = invert($tree);
say "\nInverted tree";
say "$inverted_tree\n";
display $inverted_tree;
Running the program displays the following output:
$ perl6 invert_tree2.p6
(1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v)
Tree before inversion:
1
2 3
4 5 6 7
8 9 a b c d e f
g h i j k l m n o p q r s t u v
Inverted tree:
1 3 2 7 6 5 4 f e d c b a 9 8 v u t s r q p o n m l k j i h g
1
3 2
7 6 5 4
f e d c b a 9 8
v u t s r q p o n m l k j i h g
Using a Hash of Hashes
A hash of hashes is probably the most explicit and clearest implementation of a binary tree. But it tends to be quite verbose.
A node is a hash consisting in three elements: its value (an integer), its left child and its right child. The children may be undefined when we are at the lowest level of the tree (i.e. when the node is a “leaf”). So a node could be implemented as a hash with three keys, v
(value), l
(left child) and r
(right child). The children, when they are defined, are themselves nodes, so the structure is nested and can be explored recursively. For example, the following binary tree:
1
/ \
2 3
/ \ / \
4 5 6 7
can be encoded as:
my %tree = v => 1,
l => { v => 2, l => {v => 4}, r => {v => 5} },
r => { v => 3, l => {v => 6}, r => {v => 7} },
;
In this quick and simple implementation, we use global variables for the tree and for the breadthfirst array, to avoid the pain of carrying them around back and forth in the successive recursive subroutine calls. In a reallife application, it would be more proper to pass them as arguments and return values of subroutines, or to use dynamic variables.
use v6;
my %tree = v => 1,
l => { v => 2, l => {v => 4}, r => {v => 5} },
r => { v => 3, l => {v => 6}, r => {v => 7} },
;
my @bfttree;
sub display ($tree) {
my $start = (@bfttree[*1]).elems;
my $sep_val = (2 * $start)  1;
for @bfttree > @line {
my $sep = " " x $sep_val;
say " " x $start, join $sep, @line;
$start /= 2;
$sep_val = ($sep_val  1) / 2;
}
}
sub bft (%node, $level) {
push @bfttree[$level], %node<v>;
bft(%node<l>, $level + 1) if defined %node<l>;
bft(%node<r>, $level + 1) if defined %node<r>;
}
sub invert (%node) {
invert(%node<l>) if defined %node<l>;
invert(%node<r>) if defined %node<r>;
(%node<l>, %node<r>) = %node<r>, %node<l>
if defined %node<l> and defined %node<r>;
}
bft %tree, 0;
say "Tree before inversion:";
display(@bfttree);
invert(%tree);
@bfttree = ();
bft %tree, 0;
say "\nTree after inversion";
display(@bfttree);
This program produces the following output:
$ ./perl6 invert_tree3.p6
Tree before inversion:
1
2 3
4 5 6 7
Tree after inversion
1
3 2
7 6 5 4
Alternative Solutions
Arne Sommer created a BinaryNode
class to store the tree node data structure, along with a swap
method to invert left and right children:
class BinaryNode
{
has Int $.value;
has BinaryNode $.left is rw;
has BinaryNode $.right is rw;
method swap
{
(self.left, self.right) = (self.right, self.left);
}
}
His recursive traverse
subroutine is fairly simple:
sub traverse ($current)
{
$current.swap;
traverse($current.left) if $current.left.defined;
traverse($current.right) if $current.right.defined;
}
The following subroutine (with its lexical recursive doit
subroutine) is used to prepare the tree display:
sub tree2string ($tree)
{
my @level;
my $level = 0;
sub doit($current, $level)
{
say ":: " ~ $current.value if $verbose;
@level[$level].push($current.value);
doit($current.left, $level +1) if $current.left.defined;
doit($current.right, $level +1) if $current.right.defined;
}
doit($tree, $level);
return @level.join("  ").join(" ");
}
Arne also wrote another version with just one actual code line:
unit sub MAIN ($tree = "1  2 3  4 5 6 7");
say $tree.split("  ")>>.words>>.reverse>>.join(" ").join("  ");
which produces the following output:
$ raku inverttreeoneliner "5  4 8  11 * 13 9  7 2 * * * 1"
5  8 4  9 13 * 11  1 * * * 2 7
Kevin Colyer used a node
class to represent a tree node, with three methods:
class node {
has Int $.value;
has node $.left;
has node $.right;
has method hasleft { return $!left.defined };
has method hasright { return $!right.defined };
has method isleaf { return not ( $!left.defined or $!right.defined ) };
}
I wonder why Kevin uses the has
keyword to define his methods, but it seems to work fine.
The tree construction is a bit tedious:
my $root = node.new(value => 1,
left => node.new(value => 2, left => node.new(value =>4),right => node.new(value => 5,left => node.new(value => 10, left => node.new(value=>11) ))),
right => node.new(value=>3,left=>node.new(value=>6),right=> node.new(value=>7,left=>node.new(value => 8),right=>node.new(value => 9,right=>node.new(value=>12)) ) )
);
Tree inversion, on the other hand is quite simple:
sub inverttree($node) {
return if not $node.defined;
return node.new(value => $node.value, left=>inverttree($node.right),right => inverttree($node.left));
}
For preparing the prettyprinting, Kevin’s program converts the tree to an array:
sub treetoarray($tree,@array,$parent=0,$depth=0) {
state $maxdepth;
# reset maxdepth on call to root node
$maxdepth=0 if $parent==0;
@array[$parent]=$tree.value;
my $d=$depth;
if $tree.hasleft {
$d= treetoarray($tree.left,@array,$parent*2+1,$depth+1)
}
if $tree.hasright {
$d=treetoarray($tree.right,@array,$parent*2+2,$depth+1)
}
$maxdepth=max($d,$maxdepth);
return $maxdepth;
}
But I won’t quote here Kevin’s prettyprinttree
subroutine, as it is about 70line long. Please follow the link if you want to see it.
Luca Ferrari implemented a simple Node
class:
class Node {
has Int $.value;
has Node $.left is rw;
has Node $.right is rw;
}
The tree inversion is done in the following switch
recursive subroutine:
sub switch( Node $currentnode is rw ) {
return if ! $currentnode
&& ! $currentnode.left
&& ! $currentnode.right;
my ( $left, $right ) = ( $currentnode.left, $currentnode.right );
$currentnode.left = $right;
$currentnode.right = $left;
switch( $currentnode.left ) if $currentnode.left;
switch( $currentnode.right ) if $currentnode.right;
}
Simon Proctor wrote a fullfledged objectoriented program, with three classes, one role and even one grammar. the BTree
defines most of the method used in the program:
role BTree[::T] {
has T $.value is required;
has BTree @!nodes[2];
method Str( ) {
( $!value , @.nodes.map( { "({$_})" } ) ).join("");
}
method nodes() {
@!nodes.grep({defined $_});
}
method children() {
@.nodes.elems;
}
method gist() {
BTreeRep.new( tree=>self ).gist();
}
method traverse() {
gather {
if ( self.children ) {
for @.nodes > $n {
for $n.traverse > @t {
take ($!value, @t);
}
}
} else {
take ( $!value, );
}
}
}
multi method reverse( ::?CLASS:D: ) {
self.new(
value => $!value,
nodes => @.nodes.reverse.map( *.reverse )
)
}
multi method fromStr('') { BTree }
multi method fromStr( ::?CLASS:U: Str $in ) {
my $match = BTreeGrammar.parse( $in );
if ( $match ) {
self.new(
value => $match<tree><value>.Str,
nodes => [
self.fromStr( $match<tree><left> ?? $match<tree><left>.Str !! '' ),
self.fromStr( $match<tree><right> ?? $match<tree><right>.Str !! '' )
]
);
} else {
die "Unable to Parse $in";
}
}
}
The recursive reverse
method shown above does the main work.
This role is applied to the UBTree
class UBTree does BTree[UInt] {
submethod BUILD ( UInt() :$value, :@nodes ) {
$!value = $value;
@!nodes = @nodes;
}
}
For those who don’t know, the default BUILD
submethod is automatically called by the new constructor method. Here, it is necessary to redefine the BUILD submethod to properly initialize the class’s private attributes.
Note that the fromStr
method of the BTree
role uses a grammar, BTreeGrammar
, to parse the input string representing the input binary tree:
# Example tree 5(4(11(7)(2)))(8(13)(9(1)))
grammar BTreeGrammar {
token TOP { <tree> };
token tree { <value> ["(" $<left>=<tree> ")"]? ["(" $<right>=<tree> ")"]? };
regex value { <[()]>+ }
}
Simon’s ASCIIart tree representation is quite nice, as shown in this sample output:
Tree :
5
┌─┴──┐
4 8
┌─┘ ┌┴─┐
11 13 9
┌┴┐ ┌┘
7 2 1
Reversed :
5
┌──┴───┐
8 4
┌─┴─┐ ┌─┘
9 13 11
┌┘ ┌┴┐
1 2 7
Shahed Nooshmand used a hash of hashes and managed to write the tree inversion program in the form of a Raku oneliner:
raku e 'say (sub ($_) { .isa(Pair) ?? (.key => .value.reverse.map: { samewith $^a }) !! $_ })(1 => (2 => (4, 5), 3 => (6, 7)))'
1 => (3 => (7 6) 2 => (5 4))
Quite impressive!
Colin Crain‘s submission starts again (as often) with a long comment explaining with quite a bit of details the various things he considered for solving the task. Please follow the link, it is really an interesting reading. I would really wish that Colin will stop putting these very useful comments in his code and thus let it somewhat buried in GitHub, and will start a blog having more visibility. Anyway, like with the sum path task of last week, Colin decided to use a data structure reducing a binary tree to a specific fixedsize array, with indices allocated along a levelfirst traversal of the tree for each possible node at every level. Essentially, Colin is using what I have called a flat array with an implicit data structure (or binaryheaplike array) in the description of my solution.
Inverting a tree in this format is reduced to selecting out the various levels within the array, reversing them and reconstituting the structure. This is accomplished in the following invert_tree
subroutine:
sub invert_tree (@tree) {
## symmetrically mirrors a binary tree on the right/left axis
## I wouldn't use the word "invert" here
my $max_level = get_level( @tree.end );
my @output;
for 0..$max_level > $level {
my $level_size = 2 ** $level;
my @level = @tree.splice( 0, $level_size );
@output.append: @level.reverse;
}
@tree = @output;
}
Colin made a very nice job to pretty print the tree, even with relatively deep trees, but I won’t quote here the 70+ lines of hairy code needed. Please follow the link if you want to to see it. Suffice it to show here how the array (5, 4, 8, 1, Int, 3, 9, 7, 2, Int, Int, Int, Int, Int, 1)
is displayed in Colin’s program:
______5______
/ \
__4 __8__
/ / \
1 3 9
/ \ \
7 2 1
Javier Luque wrote a fullfledged objectoriented program, with a BTree
class that has a Node
class composed into it and a number of methods, including the printtree
and recursive inverttree
multi methods to do the work:
class BTree {
my class Node {
has Int $.value is rw;
has Node $.left is rw;
has Node $.right is rw;
};
has Node $.root is rw;
# Create the binary trees
multi method createbtree($data) {
self.root = Node.new;
self.createbtree($data, self.root)
}
multi method createbtree($data, Node $node) {
$node.value = $data.[0];
# Left branch
if ($data.[1].[0]) {
$node.left = Node.new();
self.createbtree($data.[1].[0], $node.left);
}
# Right branch
if ($data.[1].[1]) {
$node.right = Node.new();
self.createbtree($data.[1].[1], $node.right);
}
}
# Print the tree
multi method printtree() {
self.printtree(self.root);
}
multi method printtree(Node $node) {
my $left = ($node.left) ??
self.printtree($node.left) !!
Nil;
my $right = ($node.right) ??
self.printtree($node.right) !!
Nil;
my $lists = ($left  $right) ??
' => ' ~ "[ $left, $right ]" !!
'';
return $node.value ~ $lists;
}
# Invert the tree
multi method inverttree() {
self.inverttree(self.root);
}
multi method inverttree(Node $node) {
# Branch left
self.inverttree( $node.left )
if ($node.left);
# Branch right
self.inverttree( $node.right )
if ($node.right);
# Invert
my $temp = $node.left;
$node.left = $node.right;
$node.right = $temp;
}
}
Mohammad S. Anwar used a hash of arrays of arrays to represent the binary tree and the mirror
recursive subroutine to perform the tree inversion:
my $tree = {
1 => [ [ 2,
[ [ 4 ],
[ 5 ],
],
],
[ 3,
[ [ 6 ],
[ 7 ],
],
],
],
};
say sprintf("Before: %s", $tree.raku);
mirror($tree.{1});
say sprintf("After : %s", $tree.raku);
sub mirror($branch) {
($branch.[0], $branch.[1]) = ($branch.[1], $branch.[0]);
mirror($branch.[0][1]) if defined $branch.[0][1];
mirror($branch.[1][1]) if defined $branch.[1][1];
return $branch;
}
Ruben Westerberg used a hash of hashes to represent the binary tree:
my $tree={
v=>1,
l=>{
v=>2,
l=>{
v=>4
},
r=>{
v=>5
}
},
r=>{
v=>3,
l=>{
v=>6
},
r=>{
v=>7
}
}
};
Rather than using a recursive subroutine, Ruben used a stack to walk through the tree depthfirst:
my @stack=($tree);
while @stack {
given (@stack.shift) {
if all .{<l r>}:exists {
my $t=.<l>;
.<l>=.<r>;
.<r>=$t;
@stack.push: .<l>;
@stack.push: .<r>;
say $_;
}
}
}
Ulrich Rieke used what I called a flat array (or binaryheaplike data structure) to represent and create the binary tree:
sub createTree( Int $depth ) { return (1..(2 ** $depth)  1 ).Array ; }
With the choice of this data structure, the inverTree
subroutine doesn’t need recursion and can use simple for
loops:
sub invertTree( @array ) {
my @inverted ;
my $depth = log( @array.elems + 1 , 2 ) ;
for ( 0..$depth  1 ) > $i {
my @partialarray ;
my $howmany = 2 ** $i ;
if ( $howmany == 1 ) {
@partialarray.push( @array.shift ) ;
}
else {
for (1..$howmany) {
@partialarray.push( @array.shift ) ;
}
}
@partialarray .= reverse ;
@inverted.push( @partialarray ) ;
}
return @inverted.flat ;
}
sub MAIN( Int $depth ) {
say invertTree( createTree( $depth ) ) ;
}
I admit that this is sort of nitpicking, but the structure of the inverted tree is not the same as the structure of the input array.
For example, with a depth of 4, the input array is represented as this flat array:
[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15]
But the output array is an array of arrays like so:
([1] [3 2] [7 6 5 4] [15 14 13 12 11 10 9 8])
Flattening this should not be very difficult.
SEE ALSO
Five blog posts on the subject:

Arne Sommer: https://rakumusings.com/invertedprefix.html;

Luca Ferrari: https://fluca1978.github.io/2020/04/20/PerlWeeklyChallenge57.html;

Shahed Nooshmand: https://rafraichisso.ir/2020/04/22/pwc57;

Javie Luque: https://perlchallenges.wordpress.com/2020/04/20/perlweeklychallenge057/;

Mohammad S. Anwar: https://perlweeklychallenge.org/blog/weeklychallenge057.
Wrapping up
Please let me know if I forgot any of the challengers or if you think my explanation of your code misses something important (send me an email or just raise an issue against this GitHub page).
If you want to participate to the Perl Weekly Challenge, please connect to this site.