Binary tree depth

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).

Examples

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

Analysis

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.

Peter's blog post is pure task analysis which is, again, one of the benefits of having a blog post. Thanks Peter for sharing your thought process.

Try it 

#!/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;
            }
        }
    }
}

27 lines of code

Output from script

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