Locate a leaf
and rob a road
Weekly challenge 151 — 7 February 2022
Week 151: 7 Feb 2022
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
The first challenge is to parse the input string into a more workable form. I chose to use
$y
to represent the rows (0 at the top) and $x
the nodes within each row (0 at the left). I then tokenised
the input string as '|', '*' or a (positive or negative) integer, and stored the integer values
in $node[$x][$y]
, leaving the unpopulated nodes undefined.
Thus the children of node ($y, $x)
are ($y + 1, 2 * $x)
and($y + 1, 2 * $x + 1)
and the task resolves to nested loops of $y
and $x
, wherein the first populated node
which has two unpopulated children is the highest leaf, and the answer to the task is thus
$y + 1
.
This is an updated solution which handles multidigit and negative node values.
#!/usr/bin/perl # Peter Campbell Smith - 2022-02-7 revised 2024-06-17 # PWC 151 task 1 use v5.28; use strict; use utf8; my (@tests, $test, $y, $x, @node, $y_max); @tests = ('1 | 2 3 | 4 5', '1 | 2 3 | 4 * * 5 | * 6', '1|1 1|1 1 1 1|1 1 1 1 1 1 1 1|1 1 * 1'); for $test (@tests) { say qq[\nInput: '$test']; # create $node->{$y)->{$x} = value $y = $x = 0; undef @node; while ($test =~ m/(\||\*|\-?\d+)/g) { # | = start a new row if ($1 eq '|') { $y ++; $x = 0; # * = leave entry undefined } elsif ($1 eq '*') { $x ++; # number = populated node } else { $node[$y][$x] = $1; $x ++; } } $y_max = $y; # look for the first node with no children TRY: for $y (0 .. $y_max) { for $x (0 .. 2 ** $y - 1) { # skip unpopulated node next unless defined($node[$y][$x]); # check populated node for 2 children unless (defined($node[$y + 1][2 * $x]) or defined($node[$y + 1][2 * $x + 1])) { say qq[Output: ] . ($y + 1) . qq[ as node($y, $x) is a leaf]; last TRY; } } } }
Input: '1 | 2 3 | 4 5' Output: 2 as node(1, 1) is a leaf Input: '1 | 2 3 | 4 * * 5 | * 6' Output: 3 as node(2, 3) is a leaf Input: '1|1 1|1 1 1 1|1 1 1 1 1 1 1 1|1 1 * 1' Output: 4 as node(3, 2) is a leaf
Any content of this website which has been created by Peter Campbell Smith is in the public domain