  The data arrangement problem on regular trees (DAPT) consists in assigning
the vertices of a given graph G, called the guest graph, to the leaves of a
d-regular tree T, called the host graph, such that the sum of the pairwise
distances of all pairs of leaves in T which correspond to the edges of G is
minimised. Luczak and Noble have shown that this problem is NP-hard for every
fixed d greater than or equal to 2. In this paper we show that the DAPT remains
NP-hard even if the guest graph is a tree, an issue which was posed as an open
question in by Luczak and Noble.
  We deal with a special case of the DAPT where both the guest and the host
graph are binary regular trees and provide a 1.015-approximation algorithm for
this special case. The solution produced by the algorithm and the corresponding
value of the objective function are given in closed form. The analysis of the
approximation algorithm involves an auxiliary problem which is interesting on
its own, namely the k-balanced partitioning problem (kBPP) for binary regular
trees and particular choices of k. We derive a lower bound for the later
problem and obtain a lower bound for the original problem by solving hG
instances of the k-BPP, where hG is the height of the host graph G.
