In this paper we investigate the average Horton-Strahler number of all possible tree-structures of binary tries. For that purpose we consider a generalization of extended binary trees where leaves are distinguished in order to represent the location of keys within a corresponding trie. Assuming a uniform distribution for those trees we prove that the expected Horton-Strahler number of a tree with α internal nodes and β leaves that correspond to a key is asymptotically given by 4 2β-α  log(α)(2β - 1)(α + 1)(α + 2) (2α+1 a-1) 8√πα 3/2 log(2)(β - 1)β( 2β  β ) 2  provided that α and β grow in some fixed proportion p when α → ∞. A similar result is shown for trees with α internal nodes but with an arbitrary number of keys.
['Markus E. Nebel']
On the Horton-Strahler number for combinatorial tries