Binary tree diameter

You are given binary tree such as below:

    1
   / \
  2   5
 / \ / \
3  4 6  7
       / \
      8  10
     /
    9

Write a script to find the diameter of the given binary tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. It doesn’t have to pass through the root.

Examples

For the tree shown above, possible diameters of 6 are:
3, 2, 1, 5, 7, 8, 9
or
4, 2, 1, 5, 7, 8, 9

Analysis

My solution simply follows all possible paths from any starting node to any ending node, and finds the longest. Of course this isn't the fastest way to do it - for example the search could be confined to start and end at nodes with only one link - but it's simple using recursion and fast enough for any 'real' example.

Try it 

Try running the script with any input:

Your $tree =

example: [1, 2], [1, 3], [3, 4, 5]

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-08-09
use utf8;     # Week 125 - task 2 - Binary tree diameter
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

my (%links, $max_length, $best_path);
# args are [parent, child (, child)]
binary_tree_diameter([[1, 2, 5], [2, 3, 4], [5, 6, 7], [7, 8, 10], [8, 9]]);
binary_tree_diameter([[1, 2, 8], [2, 3, 6], [3, 4, 5], [6, 7], [8, 9], [9, 10],
    [7, 11], [11, 12]]);

sub binary_tree_diameter {
    
    my ($tree, $t, @t, $j, $length, $path, $start);
    
    $tree = shift;
    
    # create $links[$id] = array of child and parent links
    %links = ();
    for $t (@$tree) {
        $links{$t->[0]} .= $t->[1] . ',';
        $links{$t->[1]} .= $t->[0] . ',';
        if (defined $t->[2]) {
            $links{$t->[0]} .= $t->[2] . ',';
            $links{$t->[2]} .= $t->[0] . ',';
        }
    }
    for $t (sort keys %links) { $links{$t} = substr($links{$t}, 0, -1); }

    # recurse over all start nodes
    $max_length = 0;
    $best_path = '';
    for $start (sort keys %links) {
        ($length, $path) = find_path($start, qq[¦$start¦]);
    }
    
    # tidy up and show results
    $best_path =~ s|.(.*).|$1|;
    $best_path =~ s|¦| -> |g;
    print qq[\nInput:  ];
    $j = '';
    for $t (@$tree) {
        print qq[$j$t->[0] -> $t->[1]];
        print qq[, $t->[2]] if $t->[2];
        print qq[\n];
        $j = '        ';
    }
    printf(qq[Output: %s ... %s\n], ($max_length - 1), ($best_path));
}

sub find_path {
    
    # inputs start point, length to there
    # returns length, max path
    
    my ($start, $path, @next, $this, $length, $new_path, $ok);
    
    # is this the longest path?
    ($start, $path) = @_;   
    $length = () = $path =~ m|¦|g;
    if ($length - 1 > $max_length) {
        $max_length = $length - 1;
        $best_path = $path;
    }

    # add another link to the path - if possible
    @next = split(',', $links{$start});
    for $this (@next) {
        next if $path =~ m|¦$this¦|;
        ($length, $new_path) = find_path($this, qq[$path$this¦]);
    }
    return ($length, $path);
}

36 lines of code
Completed after the closing date and not submitted to GitHub

Output from script

Input:  1 -> 2, 5
        2 -> 3, 4
        5 -> 6, 7
        7 -> 8, 10
        8 -> 9
Output: 6 ... 3 -> 2 -> 1 -> 5 -> 7 -> 8 -> 9

Input:  1 -> 2, 8
        2 -> 3, 6
        3 -> 4, 5
        6 -> 7
        8 -> 9
        9 -> 10
        7 -> 11
        11 -> 12
Output: 8 ... 10 -> 9 -> 8 -> 1 -> 2 -> 6 -> 7 -> 11 -> 12