$3\mathrm{.}2$

Let

be the undirected binary tree $($see example in problem $3\mathrm{.}1).$ For each pair of vertices, we can compute the distance between these vertices. In figure in $3\mathrm{.}1,$ for example, we have

dist$(4,17)=7.$ The diameter of T to be the maximum$$ value of dist$($x$,$y$),$ chosen over all pairs of vertices x and y in T$.$ In Java,

a$.$ create an algorithm, BFS$($vertex$2$ G$[],$ vertex$2$ s$),$ to compute the diameter of T $(25$ points$)$

Input for the tree build can be $2$ arrays that represent the edges, e$.$g$.$ for figure in $3\mathrm{.}1(1$ to $2,1$ to $3,2$ to $4,2$ to $5,...)$:

int V$[]=$ new int$[]\{1,1,2,2,3,3,6,6,7,7,8,8,10,10,11,13\}$;

int N$[]=$ new int$[]\{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17\}$;

Then, to build a tree G use this:

int order $=17$; $//$ example where max in V and N is $17$

vertex$2$ G$[]=$ new vertex$2[$order$]$;

for$($int i $=0$; i $<$ G$.$length; i$++)\{$

G$[$i$]=$ new vertex$2($i $+1)$;

$\}$

for$($int i $=0$; i $<$ V$.$length; i$++)\{$

if$($G$[$V$[$i$]-1].$nghs$[0]<0)\{$

G$[$V$[$i$]-1].$nghs$[0]=$ N$[$i$]-1$;

$\}$

else if$($G$[$V$[$i$]-1].$nghs$[1]<0)\{$

G$[$V$[$i$]-1].$nghs$[1]=$ N$[$i$]-1$;

$\}$

$\}$

And

public class vertex$2\{$

final int key;

int color, d;

int nghs$[]=$ new int$[2]$;

public vertex$2($int k$)\{$

key $=$ k;

color $=0$;

d $=0$;

nghs$[0]=-1$;

nghs$[1]=-1$;

$\}$

$\}$

b$.$ explain how your algorithm works $(5$ points$)$