then this structure can be all over the heap, where each node provides a tiny amount of information and sends us to another random location on the heap.
Is there a way to represent these "recursive expression trees" in a cache friendly structure?
(If you believe this is premature optimization, I'm open to that too, but please provide a detailed argument instead of just stating it.)
A kind of bump allocator could work, as well. Do you need to delete individual expressions or only the whole tree at once? For the latter case, bumpalo seems like a good choice.