The hypercube is a good host graph into which other structures such as arrays, rings and binary trees can be embedded. It has been shown that a complete binary tree of level h+1, T_h+1 with 2^h+1-1 nodes, can be embedded into an h-dimensional hypercube with dilation 2, congestion 2 and load 3. This paper presents an optimal algorithm that embeds T_h into an n-dimensional hypercube (h>n*1) with dilation 2, congestion 2 and load 2^h-n.

Keywords: embedding, complete binary tree, hypercube

Received April 8, 1995; revised September 24, 1995.
Communicated by Shing-Tsaan Huang.
^*Supported by National Science Council of R.O.C. under grant NSC85-2213-E009-052.