Embedding certain height-balanced trees and complete pmpm-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⩾1m⩾1, a complete pmpm-ary tree of height h   is embeddable into a hypercube of dimension O(mh)O(mh) 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].