[jholman]

There are at least two obvious alternatives to (fully) deepcloning.

First, many "everything must be immutable" libraries provide data structures that give operations that feel like mutations (but actually are not), and many of those can re-use all the old objects that are not mutated. This could save a lot, relative to full naive deepcopies. Or it could save very little, depending on what you're doing.

Second, if you have the ability, you can always mutate before recursion and then revert when the recursion finishes. This could potentially be very tricky, because it's not always easy to revert mutations. As such, it's not a good plan for a prototype, but if you can get it right, this could make your tree search wayyyyy faster.