No Diving in the Shallow End

Wherein we discover how little depth there is when it sneaks up and smacks you hard in the face.

THE WEEKLY CHALLENGE – PERL & RAKU #151 – TASK 1



“A life spent entirely in public, in the presence of others, becomes, as we would say, shallow” 
― Hannah Arendt


Binary Tree Depth

Submitted by: Mohammad S Anwar

You are given binary tree.

Write a script to find the minimum depth.

The minimum depth is the number of nodes from the root to the nearest leaf node (node without any children).

Example 1:
Input: '1 | 2 3 | 4 5'

                1
               / \
              2   3
             / \
            4   5

Output: 2
Example 2:
Input: '1 | 2 3 | 4 *  * 5 | * 6'

                1
               / \
              2   3
             /     \
            4       5
             \
              6
Output: 3

Method

So… the robust way or the easy way? Which is to say do we build a tree model, perform a depth-first traversal and note the level of each node, keeping a running minimum tally on all leaves we find? Or do we simply work the given serialized flat input instead? Because if we look at it properly, the flattened form already is a tree.

In the serialized binary tree format we have a breath-first order laid out left-to-right, with each node allocated placement for two children whether they are instantiated or not. This in turn fixes positional information within the tree, which can then be directly queried. The format can, in certain circumstances, make tree-related tasks much easier.

But let’s backtrack a bit first, to the beginning. Right out of the gate, the key difference we note about this particular tree challenge is that here we are given example input, being a variation on the serial format outlined above. In this version, the tree is encoded as a single string, with levels separated by vertical pipes and individual nodes separated by spaces. Empty node placeholders are indicated by asterisks; in this way the segment from the second example “| 4 * * 5 |” reveals the third level has four nodes, with the middle two null.

An exception for brevity is made at the end of the string, with any remaining null nodes that would fill out the level left implicit and not expressly signified, as long as there is no more real data following. Although no examples exist, the format requires child nodes of a null node to also be symbolized yet null, and so indicated with asterisks. This is necessary to unambiguously mark individual node placement within the structure.

All this carefully defined structure amounts to a parsable flat format where the child nodes have a mathematical relationship to the indices of the parent: the nodes are considered as indexed elements within a sequence, and the child nodes for a parent at some index n will be always located at indices 2n+1 and 2n+2.

When we traverse the tree from the root at index 0, checking the nodes from left to right, if we find both children to be null then we are at a terminus and have found a leaf. As the levels systematically ascend from left-to-right, the first such leaf found will have the minimum distance form the root node at index 0, and hence the minimum depth.

So to answer the opening question, I say we do it the easy way.

PERL 5 SOLUTION

The processing in broken down into two sections.

First off we parse the input string, converting it into an array of node elements, with null nodes assigned indices yet left undefined. Then the minimum depth can be determined by searching this array from the root node to the first node without children, looking forward to the child node positions. Along the way a counter does the bookkeeping to keep rack of the current level. Each level contains 2n-1 elements, so every time we iterate another index position we tick a counter, and when the counter reaches the level limit the level is incremented and the counter reset.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';


my $input = shift ;
say mindepth( parse($input) ) if defined $input;;

sub parse ( $input ) {
    return map { $_ eq '*' ? undef : $_ } 
           grep { $_ ne '|' } 
           split ' ', $input;
}

sub mindepth ( @tree ) {
    my $level = 1 ;
    my $count = 0 ;
    
    for my $idx ( 0 .. $#tree ) {
        return $level if ( defined $tree[$idx]  
                            and not defined $tree[$idx * 2 + 1]
                            and not defined $tree[$idx * 2 + 2] ) ;
        $level++ and $count = 0 if ++$count == 2 ** ($level-1) ;    
    }
}

raku solution

Raku uses an arguably more-precise idea of a class Nil, sort of a dev/null of classes: a Nil can contain only one possible value, Nil, and anything assigned to is becomes Nil as well. Because it is a proper class, derived from Mu, through first Any and then Cool, it inherits a whole raft of methods, which adapt themselves to act accordingly and drop any outside data into the black-hole that is Nil. It’s all very consistent, if not particularly exciting. Of note the myriad warnings that arise when trying to apply the many Nil methods are pretty creative in the number of ways you can say: “You know you’re trying to append to something that isn’t there, don’t you?” and similar.

unit sub MAIN ( $input = '1 | 2 3 | 4 *  * 5 | * 6' ) ;

say mindepth( parse( $input ) );

sub parse ( $input ) {
    $input  .split(/\s+/)
            .grep( * ne '|')
            .map: {$_ eq '*' ?? Nil !! $_} ;
}

sub mindepth ( @tree ) {
    my ( $level, $count ) = ( 1, 0 );
    for @tree.keys -> $idx {
        return $level if @tree[$idx].defined 
                        and not @tree[$idx * 2 + 1].defined 
                        and not @tree[$idx * 2 + 2].defined ;
                        
        $level++ and $count = 0 if ++$count == 2 ** ($level-1);
    }
}



The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s