Abstract
Assume that in one unit of time a node is stored in the stack or is removed from the top of the stack during postorder-traversing of a binary tree. If all binary trees are equally likely the average stack size aftert units of time and the variance is computed as a function of the proportionϱ=t/n.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Abramowitz and I. A. Stegun,Handbook of Mathematical Functions, Dover Publications, INC, New York, 1970.
T. M. Apostol,Introduction to Analytic Number Theory, Springer Verlag, New York, 1976.
L. Carlitz, D. P. Roselle and R. A. Scoville,Some remarks on ballot-type sequences of positive integers, J. Comb. Theory, Ser. A. 11 (1971), 258–271.
N. G. deBruijn, D. E. Knuth and S. O. Rice,The Average Height of Planted Plane Trees, R. C. Read (Ed.), Graph Theory and Computing, New York, London, Ac. Press (1972), 15–22.
R. Kemp,On The Average Stack Size of Regularly Distributed Binary Trees, H. A. Maurer (Ed.), Lect. Notes in Comp. Sci. 71 (1979), 340–355.
D. E. Knuth,The Art of Computer Programming, Vol. 1, 2nd ed., Addison-Wesley, Reading, 1973.
G. Kreweras,Sur les éventails de segments, Cahiers du B.U.R.O. 15, Paris, (1970), 1–41.
J. Riordan,Combinatorial Identities, Wiley, New York, 1968.
Author information
Authors and Affiliations
Additional information
Part of this paper was presented at the 6th Colloquium on Automata, Languages and Programming, ICALP' 79, July 1979.
Rights and permissions
About this article
Cite this article
Kemp, R. A note on the stack size of regularly distributed binary trees. BIT 20, 157–162 (1980). https://doi.org/10.1007/BF01933188
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01933188