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.
The Latest from CACM
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More
Join the Discussion (0)
Become a Member or Sign In to Post a Comment