Task — 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

I did not submit a solution at the time, but have written this later.

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);
}

Output

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