# Challenge 56 - Diff-K and Binary Trees

Responding to Perl Weekly Challenge #56

### TASK #1 - Diff-K

You are given an array

@Nof positive integers (sorted) and another non negative integerk.Write a script to find if there exists 2 indices

iandjsuch thatA[i] - A[j] = kandi != j.It should print the pairs of indices, if any such pairs exist.

Example:

`@N = (2, 7, 9)`

`$k = 2`

Output :

`2,1`

I’m assuming the givens – sorted array of positive integers, non-negative integer, and passing an array and separating them in the signature in `( $k, @N )`

.

If `k = N[j] - N[i]`

, `k >= 0`

and `i != j`

, `k`

can only equal `0`

if there are duplicate integers, so `N[i] == N[j]`

can be true as long as `i !- j`

.

So, nested loops where `j`

is outside and `i`

is inside, starting with `j+1`

.

```
#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use feature qw{ fc postderef say signatures state switch };
no warnings qw{ experimental };
diffk( 2, 2, 7, 9 );
sub diffk ( $k, @N ) {
for my $j ( 0 .. -1 + scalar @N ) {
for my $i ( $j + 1 .. -1 + scalar @N ) {
next if $i == $j;
next unless $k == $N[$i] - $N[$j];
say join ", ", $i, $j;
}
}
}
# $ ./ch-1.pl
# 2, 1
```

### TASK #2 - Path Sum

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.

Given the below binary tree and sum = 22, the partial path sum 5 → 8 → 9 = 22 is not valid.

The script should return the path 5 → 4 → 11 → 2 whose sum is 22.

```
5
/ \
4 8
/ / \
11 13 9
/ \ \
7 2 1
```

This looks like a job for **Recursion!**

I mean, can you do iteration over a tree?

And we also need a concept of a Node, where it has a value, has children, and knows if it’s a leaf or not. I recall trees being read left-to-right, so **5->4->11->7** is read before **5->4->11->2**, so child sorting isn’t necessary. We’re keeping this tree binary by ourselves, not enforcing it within the code, so this is a fairly naive Node implementation.

I solved this once without a `parent`

link, keeping track of totals and paths, but then I thought a moment and considered the ease, and being able to trace up once you find a leaf makes the code easier. The spidering assumes an acyclic graph; I could easily make something with cycles and make it loop through forever, but that wouldn’t solve this problem, would it?

```
package Node;
sub new ( $class, $value = 0 ) {
my $self = {};
$self->{value} = $value;
$self->{children} = [];
$self->{parent} = undef;
return bless $self, $class;
}
sub value ( $self ) {
return $self->{value};
}
sub is_root ( $self ) {
return defined $self->{parent} ? 0 : 1;
}
sub is_leaf ( $self ) {
return scalar $self->{children}->@* ? 0 : 1;
}
sub add_child ( $self, $node ) {
$node->{parent} = $self;
push $self->{children}->@*, $node;
}
sub children( $self ) {
return $self->{children}->@*;
}
sub parent ($self ) {
return $self->{parent};
}
```

I tried to do `$node->add_child( new Node(8))`

but it wasn’t working for me,
so I create a hash full of nodes and create the tree that way.

```
# make the tree
my $hash->%* = map { $_ => new Node($_) } 1 .. 13;
$hash->{5}->add_child( $hash->{4} );
$hash->{5}->add_child( $hash->{8} );
$hash->{4}->add_child( $hash->{11} );
$hash->{11}->add_child( $hash->{7} );
$hash->{11}->add_child( $hash->{2} );
$hash->{8}->add_child( $hash->{13} );
$hash->{8}->add_child( $hash->{9} );
$hash->{9}->add_child( $hash->{1} );
```

Yes, there are some nodes that are created but not included, but that’s fine.

The only thing left is to traverse the tree. Once we find a leaf node, we trace it back to the root, making the total and the path as we go.

```
spider_tree( $hash->{5}, 22 );
sub spider_tree ( $node, $value ) {
if ( $node->is_leaf() ) {
my $x = $node;
my $t = $x->value();
my @p = ( $x->value() );
while ( !$x->is_root ) {
$x = $x->parent();
$t += $x->value();
unshift @p, $x->value();
}
if ( $t == $value ) {
say $t;
say join ' -> ', @p;
}
}
for my $child ( $node->children() ) {
spider_tree( $child, $value );
}
}
```

The code as a whole:

```
#!/usr/bin/env perl
use strict;
use warnings;
use utf8;
use feature qw{ postderef say signatures state switch };
no warnings qw{ experimental };
# make the tree
my $hash->%* = map { $_ => new Node($_) } 1 .. 13;
$hash->{5}->add_child( $hash->{4} );
$hash->{5}->add_child( $hash->{8} );
$hash->{4}->add_child( $hash->{11} );
$hash->{11}->add_child( $hash->{7} );
$hash->{11}->add_child( $hash->{2} );
$hash->{8}->add_child( $hash->{13} );
$hash->{8}->add_child( $hash->{9} );
$hash->{9}->add_child( $hash->{1} );
spider_tree( $hash->{5}, 22 );
sub spider_tree ( $node, $value ) {
if ( $node->is_leaf() ) {
my $x = $node;
my $t = $x->value();
my @p = ( $x->value() );
while ( !$x->is_root ) {
$x = $x->parent();
$t += $x->value();
unshift @p, $x->value();
}
if ( $t == $value ) {
say $t;
say join ' -> ', @p;
}
}
for my $child ( $node->children() ) {
spider_tree( $child, $value );
}
}
package Node;
sub new ( $class, $value = 0 ) {
my $self = {};
$self->{value} = $value;
$self->{children} = [];
$self->{parent} = undef;
return bless $self, $class;
}
sub value ( $self ) {
return $self->{value};
}
sub is_root ( $self ) {
return defined $self->{parent} ? 0 : 1;
}
sub is_leaf ( $self ) {
return scalar $self->{children}->@* ? 0 : 1;
}
sub add_child ( $self, $node ) {
$node->{parent} = $self;
push $self->{children}->@*, $node;
}
sub children( $self ) {
return $self->{children}->@*;
}
sub parent ($self ) {
return $self->{parent};
}
# $ ./ch-2.pl
# 22 22 5->4->11->2
```

A friend asked about the Word Ladder code I wrote about when engaging with Dijkstra’s Algorithm, titled “Graphs are not that Scary”, and I think this code proves that point again.