The stack-size of tries: A combinatorial study (Q5958316)

In this paper, we introduce a class of extended binary trees that resembles all possible tree-structures of binary tries. Assuming a uniform distribution of those trees we prove that for \(\alpha\) being the number of internal nodes the average stack-size is given by \(\frac 32\pi \alpha\). Since this result is quite similar to that for ordinary extended binary trees an attempt to find an explanation for that similarity using a quantitative level is made.