On Computing Distances Between Leaves in a Complete Tree

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 0(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. © 1980, Taylor & Francis Group, LLC