The usual way to do this is by using a CSPRNG to generate the leaf values, such as AES in counter mode. That way, once you have calculated the entire tree, you only need to store the upper layers, the secret AES key, and the initial counter value, and it is quite easy to recalculate very quickly any particular branch you need.
For example, let's say you generate a tree of depth 20 using AES in CTR mode to generate the values $v_0, v_1, v_2, ...v_n$ (in figure 1 on page 5 of the paper you linked), so there is a corresponding counter-value $c_i$ for each $v_i$, such that $v_i = E_K(c_i)$. Let's also say you only store the AES key, the first counter value, and the top 9 layers of the hash tree (so you only need to keep 511 hashes, and can discard the remaining 1 million or so hashes in the tree).
To recalculate the path from any one particular leaf, $v_i$, back to the top-most node, all you need to do is re-generate the leaf value for $v_i$ using AES and the counter value $c_i$ (which is easy if you know the initial counter value and the index $i$), plus 2047 of its immediate neighboring values, and then use the hash function $H$ to re-generate the branch of the tree from those 2048 values up to one of the 256 stored values in layer 9 (which takes much less time to calculate than the initial set-up because you are only doing one 256th of the tree rather than the whole tree).
