<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 4" %>
Left and Right Length of Paths in Binary Trees or on a Question of Knuth
Alois Panholzer
Institut f{\"u}r Diskrete Mathematik und Geometrie, Technische Universit\"at Wien, Wiedner Hauptstr. 8-10/104, 1040 Wien, Austria
Annals of Combinatorics 12 (4) pp.475-488 December, 2008
AMS Subject Classification: 05C05, 60F05
We consider extended binary trees and study the joint right and left depth of leaf $j$, where the leaves are labelled from left to right by $0,\, 1, \ldots,\, n$, and the joint right and left external pathlength of binary trees of size $n$. Under the random tree model, i.e., the Catalan model, we characterize the joint limiting distribution of the suitably scaled left depth and the difference between the right and the left depth of leaf $j$ in a random size-$n$ binary tree when $j \sim \rho n$ with $0<\rho<1$, as well as the joint limiting distribution of the suitably scaled left external pathlength and the difference between the right and the left external pathlength of a random size-$n$ binary tree.
Keywords: binary trees, imbalance, node depth


1. M. Bousquet-M´elou, Limit laws for embedded trees: applications to the integrated super- Brownian excursion, Random Structures Algorithms 29 (4) (2006) 475-–523.

2. P. Chassaing and S. Janson, The center of mass of the ISE and the Wiener index of trees, Electron. Comm. Probab. 9 (2004) 178-–187.

3. P. Flajolet and A.M. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (2) (1990) 216-–240.

4. I. Goulden and D. Jackson, Combinatorial Enumeration, JohnWiley & Sons Inc , New York, 1983.

5. S. Janson, The Wiener index of simply generated random trees, Random Structures Algorithms 22 (4) (2003) 337-–358.

6. S. Janson, Left and right pathlengths in random binary trees, Algorithmica 46 (3-4) (2006) 419-–429.

7. R. Kemp, Fundamentals of the Average Case Analysis of Particular Algorithms, John Wiley & Sons, Ltd., Chichester, Stuttgart, 1984.

8. C. Knessl and W. Szpankowski, Binary trees, left and right paths, WKB expansions, and Painlev´e transcendents, In: Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics, (2006) pp. 198–204; online at http://www.siam.org /proceedings/analco/2006/analco06.php.

9. D.E. Knuth, The Art of Computer Programming, Vol. 1, Fundamental Algorithms, 3rd Ed., Addison-Wesley, Reading, Massachusetts, 1997.

10. J.-F. Marckert, The rotation correspondence is asymptotically a dilatation, Random Structures Algorithms 24 (2) (2004) 118-132.

11. A. Panholzer and H. Prodinger, Descendants and ascendants in binary trees, Discrete Math. Theor. Comput. Sci. 1 (1) (1997) 247–-266.

12. A. Panholzer and H. Prodinger, Moments of level numbers of leaves in binary trees, J. Statist. Plann. Inference 101 (1-2) (2002) 267-–279.