The Expected Performance of Traversal Algorithms in Binary Trees

The paper compares expected performance measures for common traversal algorithms operating on threaded and unthreaded binary trees, under the assumption that the trees are selected from the distribution induced by random insertions. The results are shown to be similar to those derived in an earlier paper for binary trees selected from the uniform distribution.