  We investigate the statistics of extremal path(s) (both the shortest and the
longest) from the root to the bottom of a Cayley tree. The lengths of the edges
are assumed to be independent identically distributed random variables drawn
from a distribution \rho(l). Besides, the number of branches from any node is
also random. Exact results are derived for arbitrary distribution \rho(l). In
particular, for the binary {0,1} distribution
\rho(l)=p\delta_{l,1}+(1-p)\delta_{l,0}, we show that as p increases, the
minimal length undergoes an unbinding transition from a `localized' phase to a
`moving' phase at the critical value, p=p_c=1-b^{-1}, where b is the average
branch number of the tree. As the height n of the tree increases, the minimal
length saturates to a finite constant in the localized phase (p<p_c), but
increases linearly as v_{min}(p)n in the moving phase (p>p_c) where the
velocity v_{min}(p) is determined via a front selection mechanism. At p=p_c,
the minimal length grows with n in an extremely slow double logarithmic
fashion. The length of the maximal path, on the other hand, increases linearly
as v_{max}(p)n for all p. The maximal and minimal velocities satisfy a general
duality relation, v_{min}(p)+v_{max}(1-p)=1, which is also valid for directed
paths on finite-dimensional lattices.
