Heights of Butterfly Trees

ABSTRACT Binary search trees (BSTs) are fundamental data structures whose performance is largely governed by tree height. We introduce a block model for constructing BSTs by embedding internal BSTs into the nodes of an external BST—a structure motivated by parallel data architectures—corresponding to composite permutations formed via Kronecker or wreath products. Extending Devroye's result that the height of a random BST satisfies , we show that block BSTs with nodes and fixed external size satisfy in distribution. We then study butterfly trees : BSTs with nodes generated from permutations built using iterated Kronecker or wreath products. For simple butterfly trees (from iterated Kronecker products of ), we give a full distributional description showing polynomial height growth: with . For nonsimple butterfly trees (from wreath products), we prove power‐law bounds: , with .