Abstract
Two algorithms are presented and analyzed, which compute the distance between any pair of leaves of a complete tree. The first algorithm is quite efficient, running in time O(log2 distance) on a uniform-cost RAM. The second algorithm is somewhat less efficient, though it too runs on a uniform-cost RAM in time O(log2 distance); it is presented mainly because its validity depends on an interesting numerological descriptor of complete trees.
Keywords: