(fold): Don't modify tree with newly-allocated nodes; instead make new