Binary Trees are optimal… except when they’re not.

The best case depth for a search tree is , if is the arity (or branching) of the tree. Intuitively, we know that if we increase , the depth goes down, but is that all there is to it? And if not, how do we chose the optimal branching ?

While it’s true that an optimal search tree will have depth , we can’t just increase indefinitely, because we also increase the number of comparisons we must do in each node. A -ary tree will have (in the worst case) keys, and for each, we must do comparisons for lower-than and equal (the right-most child will be searched without comparison, it will be the “else” of all the comparisons). We must first understand how these comparisons affect average search time.