Skip to Main content Skip to Navigation
Conference papers

Left and right length of paths in binary trees or on a question of Knuth

Abstract : We consider extended binary trees and study the common right and left depth of leaf $j$, where the leaves are labelled from left to right by $0, 1, \ldots, n$, and the common right and left external pathlength of binary trees of size $n$. Under the random tree model, i.e., the Catalan model, we characterize the common 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 common 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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184699
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 17, 2015 - 4:06:12 PM
Last modification on : Wednesday, May 10, 2017 - 5:40:29 PM
Long-term archiving on: : Wednesday, November 18, 2015 - 12:08:10 PM

File

dmAG0136.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184699, version 1

Collections

Citation

Alois Panholzer. Left and right length of paths in binary trees or on a question of Knuth. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. pp.415-418. ⟨hal-01184699⟩

Share

Metrics

Record views

263

Files downloads

650