So, ELI5: What do you do instead, where you return a modified object, but still have immutability? Or do you avoid the problem by not trying to do that?
But if you modify the leaf, don't you also have to modify the branch node that points to the leaf, so that it points to the new one? And every node from there to the root?
Yes, you (or rather, core library developers) need to pick a data structure appropriate to your access patterns: linked lists for iteration, search trees for concatenation, finger trees for random access, and so on. But you should be doing this anyway for clarity, even if you face no performance constraints.
