Analysis of algorithms on threaded trees
Keith Brinck · The Computer Journal · 1981
This paper investigates the performances of various algorithms operating on binary trees. In particular the expected times necessary to compute the different successor and predecessor nodes of a random node in a random threaded binary tree are presented. Based on these results it is then shown that the inorder traversal algorithm using threads is about 25% better performing than the corresponding algorithm using stacks, while for preorder and postorder little or no improvement in traversal times is gained by the use of threads. Finally the presence of threads in a binary tree is briefly discussed with respect to the performance of insertion and deletion algorithms.