You are given binary tree 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.

For the above given binary tree, possible diameters (6) are:

`3, 2, 1, 5, 7, 8, 9`

or

`4, 2, 1, 5, 7, 8, 9`

The first thing we notice is that lack of description of how we are going to take input. There's an example, but everyone can see that doesn't scale to a tree of non-trivial size.

So, we have to content ourselves to create an incomplete program, where we leave constructing a tree from the input unimplemented.

(Of course, it could very well be that the intent is that we only write
a program to find the diameter of the one given tree, but surely,
`say 6`

can't be the intended solution).

And since we're writing an incomplete program, we only write a Perl solution.

How do we calculate the diameter of a tree? For that, we first define the depth of a tree: this is the length of the longest path from the root to a leaf. Recursively, we can define this as:

\[ \text{depth } (\mathcal{T}) = \begin{cases} 0 & \text{if } \mathcal{T} = \bot \\ \max \left( \begin{array}{l} \text{depth }(\mathcal{T} \rightarrow \text{left}), \\ \text{depth }(\mathcal{T} \rightarrow \text{right}) \end{array} \right) & \text{if } \mathcal{T} \neq \bot \end{cases} \]

where \(\mathcal{T} \rightarrow \text{left}\) and \(\mathcal{T} \rightarrow \text{right}\) are the left and right child of the tree \(\mathcal{T}\). \(\bot\) stands for the empty tree.

Now, the diameter of a tree \(\mathcal{T}\) either goes via the root of \(\mathcal{T}\), or is fully contained in one its children. The length of the longest possible path going through the root is equal to the sum of the depth of its children, as the longest path from a root always ends at a leaf. The diameter only goes through the root, if the longest path through the root is greater than the diameter of either of its children. Otherwise, the diameter of \(\mathcal{T}\) is the maximum of the diameters of its children. Recursively, the definition is:

\[ \text{diameter } (\mathcal{T}) = \begin{cases} 0 & \text{if } \mathcal{T} = \bot \\ \max \left( \begin{array}{l} \text{diameter }(\mathcal{T} \rightarrow \text{left}), \\ \text{depth }(\mathcal{T} \rightarrow \text{left}) + \text{depth }(\mathcal{T} \rightarrow \text{right}), \\ \text{diameter }(\mathcal{T} \rightarrow \text{right}) \end{array} \right) & \text{if } \mathcal{T} \neq \bot \end{cases} \]

We create a package `Tree`

, whose instances contain trees.
It will have two accessors, `left`

and `right`

, which return the
left and right children. Empty trees are undefined. The `init`

function,
which takes the input and constructs the tree, is left unimplemented:

```
package Tree {
use Hash::Util::FieldHash qw [fieldhash];
use List::Util qw [max];
fieldhash my %left;
fieldhash my %right;
sub new ($class) {bless do {\my $var} => $class}
sub init ($self, $input) {
...; # Yada, yada, yada
$self;
}
sub isleaf ($self) {!$left {$self} || !$right {$self}
sub left ($self) {!$self -> isleaf && $left {$self}}
sub right ($self) {!$self -> isleaf && $right {$self}}
}
```

Now we can create a method to calculate the diameter. For this, we
need a method `_diameter`

, which does a postorder walk of a tree,
returning a tuple: the first element is the depth of the tree,
the second element is the diameter. `diameter`

will be a wrapper
which calls `_diameter`

and returns the second return value:

```
package Tree {
sub _diameter ($self) {
return (0, 0) if $self -> isleaf; # Leaves have no depth nor diameter.
my ($ldp, $ldm) = $self -> left -> _diameter;
my ($rdp, $rdm) = $self -> right -> _diameter;
(max ($ldp, $rdp), max ($ldm, $rdm, $ldp + $rdp))
}
sub diameter ($self) {
($self -> _diameter ($self)) [1]
}
}
```

Our main program now becomes a single line:

```
say Tree:: -> new -> init (do {local $/; <>}) -> diameter;
```

Find the full program on GitHub.