A linear algorithm for copying binary trees using bounded workspace
K. P. Lee · Communications of the ACM · 1980
An algorithm to copy a binary tree in linear time using bounded workspace is presented. The algorithm does not modify the original tree at any time. The copy is constructed in such a way that it can be traversed in a read-only fashion even before the copying process is complete, provided one can distinguish between the original and the copy. The traversal can be carried out in parallel with the copying.