  A classical result of Koml\'os, S\'ark\"ozy and Szemer\'edi states that every
$n$-vertex graph with minimum degree at least $(1/2+ o(1))n$ contains every
$n$-vertex tree with maximum degree $O(n/\log{n})$ as a subgraph, and the
bounds on the degree conditions are sharp. On the other hand, Krivelevich, Kwan
and Sudakov recently proved that for every $n$-vertex graph $G_\alpha$ with
minimum degree at least $\alpha n$ for any fixed $\alpha >0$ and every
$n$-vertex tree $T$ with bounded maximum degree, one can still find a copy of
$T$ in $G_\alpha$ with high probability after adding $O(n)$ randomly-chosen
edges to $G_\alpha$. We extend their results to trees with unbounded maximum
degree. More precisely, for a given $n^{o(1)}\leq \Delta\leq cn/\log n$ and
$\alpha>0$, we determine the precise number (up to a constant factor) of random
edges that we need to add to an arbitrary $n$-vertex graph $G_\alpha$ with
minimum degree $\alpha n$ in order to guarantee a copy of any fixed $n$-vertex
tree $T$ with maximum degree at most~$\Delta$ with high probability.
