Oh, brilliant idea just to have a single make_immutable pass after building the tree! This is a write-once, read-many situation so that is a very easy improvement I can make.
I spent a couple of hours last night working through Serialization.jl with an eye toward a custom dispatch for serialize. In the meantime, it was easy enough to flatten the tree into a vector of Ints representing all the childvalues instances and serialize that instead. Even with the overhead of flattening and expanding, I’ve already gotten a huge increase in throughput.