On Weighted Depths in Random Binary Search Trees

Rafik Aguech, Anis Amri, Henning Sulzbach

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
116 Downloads (Pure)


Following the model introduced by Aguech et al. (Probab Eng Inf Sci 21:133–141, 2007), the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyse weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search process, the weighted path length and the weighted Wiener index in a random binary search tree. We establish three regimes of nodes depending on whether the second-order behaviour of their weighted depths follows from fluctuations of the keys on the path, the depth of the nodes or both. Finally, we investigate a random distribution function on the unit interval arising as scaling limit for weighted depths of nodes with at most one child.
Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalJournal of Theoretical Probability
Early online date11 Jul 2017
Publication statusE-pub ahead of print - 11 Jul 2017


  • Analysis of algorithm
  • Data structures
  • Binary search trees
  • Central limit theorems
  • Contraction method
  • Random probability measures


Dive into the research topics of 'On Weighted Depths in Random Binary Search Trees'. Together they form a unique fingerprint.

Cite this