Two results on linear embeddings of complete binary trees

AbstractGiven a binary tree T with n vertices, we want to embed T onto a given set A of n points on the line so as to minimize the total embedded edge length. Polynomial-time algorithms for the two following special cases of this problem can be found in the literature: 1.when T is arbitrary but A = {1…n}.2.when T is a complete binary tree and A is arbitrary. To the best of our knowledge, the complexity of the general problem is open. In this paper we deal with case (2). Bern et al. presented an algorithm for this case that runs in time O(n5.76) and uses O(n3.2) space. They also considered the naive embedding, which maps the root r of T into the middle point a of A, and then embeds, recursively, the left and right subtrees of r to the left and right of a, respectively. This is equivalent to embedding T from left to right according to the inorder traversal. They prove that this naive algorithm approximates the optimal solution within the factor of 3.The main results of this paper are: (i) the proof that the approximation ratio of this naive algorithm is exactly 73, and (ii) a more efficient algorithm for computing minimum embeddings of complete binary trees. Our algorithm runs in time O(n1 + log 3) = O(n2.59), and uses O(n) space, where O(f) = O(f logcn), for some constant c > 0