You could always clone the tree into a new linked-list if you wanted to keep things purely functional, but that would add needless complexity and still not make it easier to create a correct implementation.

Functional programming as a paradigm makes sense when you want to limit the context a programmer has to be aware of when working on a problem, but in this case recursion and imperative programming accomplish the same goal.