On the maximum edge length in VLSI layouts of complete binary trees (Q1081305)

A recently suggested layout of complete binary trees is carefully analysed to obtain an exact value for the length of its longest edge. Although the layout achieves the asymptotic lower bound of \(\Omega\) (\(\sqrt{n}/\log n)\), it is shown that as long as the tree has less than \(2^{16}\) leaves, the well-known H-tree layout having a maximum edge length of \(\Theta\) (\(\sqrt{n})\) turns out to be superior. Therefore, the H-tree layout should be preferred for most realistic tree sizes.