It is possible to implement binary search trees in a nondestructive form. It is a matter of copying the spine of the tree down to the point where the change is called for.

Memory management is more difficult with this style, though. It is best suited to a setting where there is an automatic garbage collector, so that you do not need to be concerned with memory management. In C++, you do your own memory management. Java has an automatic garbage collector.