You are given binary tree as below:
1 / \ 2 5 / \ / \ 3 4 6 7 / \ 8 10 / 9Write 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, 9or
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.