Embedding height balanced trees and Fibonacci trees in hypercubes

A height balanced tree is a rooted binary tree T in which for every vertex v ∈ V(T), the difference bT (v) between the heights of the subtrees, rooted at the left and right child of v is at most one. We show that a height-balanced tree Th of height h is a subtree of the hypercube Qh+1 of dimension h + 1, if Th contains a path P from its root to a leaf such that bTh(v) = 1, for every non-leaf vertex v in P. A Fibonacci tree Fh is a height balanced tree Th of height h in which bFh(v) = 1, for every non-leaf vertex. F h has f(h + 2) - 1 vertices where f(h + 2) denotes the (h + 2)th Fibonacci number. Since f(h) ∼ 20.694h, it follows that if F h is a subtree of Qn, then n is at least 0.694(h+2). We prove that Fh is a subtree of the hypercube of dimension approximately 0.75h. © 2008 Korean Society for Computational and Applied Mathematics.