  We analyse the potential of the proposed $\mu^+ \mu^+$ and $\mu^+ e^-$
collider $\mu$TRISTAN to complement the searches for charged-lepton
flavour-violation (CLFV) that can be carried out by Belle II. $\mu$TRISTAN
offers the possibility of directly producing and studying new resonances that
could mediate CLFV for a certain range of masses. In addition, we find that it
can produce competitive bounds to those from Belle II for cases where the new
resonance lies beyond direct reach. We illustrate these points with three $Z_3$
"lepton triality" models, where we also find an example that can only be probed
by $\mu$TRISTAN. These three models feature doubly-charged scalars, denoted
$k_{1,2,3}$ respectively, that induce both CLFV and flavour-conserving
processes. Tree-level $k_1$ exchange induces the CLFV scattering process $\mu^+
e^- \to e^+ \tau^-$, while $k_2$ interactions induce $\mu^+ \mu^+ \to \tau^+
e^+$, $\mu^+ e^- \to \tau^+ \mu^-$ and make a non-SM contribution to the
flavour-conserving scattering $\mu^+ \mu^+ \to \mu^+ \mu^+$. The $k_3$ model
has a non-SM contribution to the flavour-conserving process $\mu^+ e^- \to
\mu^+ e^-$. Other scattering processes involving $k_1$, $k_2$ or $k_3$ are not
relevant for $\mu$TRISTAN and outside the scope of our analysis. We quantify
the sensitivity of $\mu$TRISTAN for each of these processes. For the $k_1$ and
$k_2$ cases we compare the $\mu$TRISTAN reach to the expected sensitivity of
Belle II to the crossing symmetry related CLFV $\tau$ decays.
