Binary search trees (BSTs) are a fundamental data structure, optimized for data retrieval, entry, and deletion as needed for priority queue tasks. A fundamental statistic that controls each of these operations is the height of the tree with $n$ nodes, $h_n$, which returns the maximal depth of a node within the tree. Devroye established the height of a random BST, generated using a uniform permutation of length $n$, has height that limits to $c^*\approx 4.311$ when scaled by $\log n$. We are interested in studying the  heights of random block BSTs, $h_{n,m}$, which correspond to uniform permutations combined using Kronecker or wreath products of permutations of lengths $n$ and $m$, that thus arise naturally in the setting of a BST data structure implemented using parallel architecture. We show using one such product of two permutations suffices to increase the asymptotic height of a random BST, while maintaining a logarithmic scaling with respect to the length of the generated permutation. We then explore the question of how much can the height increase when repeatedly using such products. These butterfly trees correspond to block BSTs formed using uniform butterfly permutations, that include a particular 2-Sylow subgroup of the symmetric group of $N = 2^n$ objects formed by taking $n$-iterated wreath products of $S_2$. In this setting, we show the expected heights for the corresponding block BSTs are now polynomial, with a lower bound of $N^\alpha$ for $\alpha \approx 0.585$. We provide exact nonasymptotic and asymptotic distributional descriptions for the case of simple butterfly permutations, which also include connections to other well-studied permutations statistics (e.g., the longest increasing subsequence, number of cycles, left-to-right maxima), while for nonsimple butterfly permutations we provide power-law bounds on the expected heights. This project is joint with Chenyang Zhong.