Embedding certain height-balanced trees and complete pm p m -ary trees into hypercubes
A height-balanced tree is a rooted binary tree T  in which for every vertex v?V(T) v ? V ( T ) , the heights of the left and right subtrees of v, differ by at most one. In this paper, we embed two subclasses of height-balanced trees into hypercubes with unit dilation. We also prove that for certain values of p  and for all m?1 m ? 1 , a complete pm p m -ary tree of height h  is embeddable into a hypercube of dimension O(mh) O ( m h ) with dilation O(m) O ( m ) using the embedding results of the above height-balanced trees. These results improve and extend the results of Gupta et al. (2003) [10].
embedding height-balanced trees hypercube complete k-ary trees