Path length of protected nodes in random binary search trees

Document Type : Full Length Article

Authors

‎Department of Statistics‎, ‎Faculty of Science‎, ‎Imam Khomeini International University‎, ‎Qazvin‎, I. R. ‎Iran

Abstract

A protected node is a node that is not a leaf and none of its children is a leaf, and also a weakly protected node is not a leaf and at least one of its children is not a leaf. Let Pn and Wn be the path length of the protected and weakly protected nodes in a random binary search tree (BST) of size n, respectively. In this paper, we derive the exact mean and variance of these random variables and show that
$$\frac{15 Pn}{11n\ln n}\to 1$$
and
$$\frac{15W_n}{14n\ln n}\to 1$$
in probability.

Graphical Abstract

Path length of protected nodes in random binary search trees

Keywords

Main Subjects


[1] M. Bona, k-protected nodes in binary search trees. Adv. Appl. Math. 53 (2014) 1–11.
https://doi.org/10.1016/j.aam.2013.09.003
[2] A. M. Frieze, M. Karonski, Introduction to Random Graphs, 1st Edition, Cambridge University Press, 2016. https://doi.org/10.1017/mag.2017.110
[3] R. Kazemi, On the Zagreb index of random m-oriented recursive trees, TOC. 12(2) (2023) 93–105.
https://doi.org/10.22108/TOC.2022.132750.1964
[4] R. Kazemi, L. Meimondari, Degree distance and Gutman index of increasing trees, TOC. 5(2) (2016)
23–31. https://doi.org/10.22108/toc.2016.9915
[5] D. E. Knuth, The Art of Computer Programming, second ed., in: Sorting and
Searching, vol. 3, Addison-Wesley, Reading, MA, 1998, Originally published in 1973.
https://dl.acm.org/doi/book/10.5555/280635
[6] H. M. Mahmoud, Sorting: A Distribution Theory, Wiley, New York, NY, 2000.
https://doi.org/10.1002/9781118032886
[7] H. M. Mahmoud, Evolution of Random Search Trees, Wiley, New York, NY, 1992.
https://www. semanticscholar .org/ paper/ Evolution-of-random-search-trees- Mahmoud/
965a46ba9d339bad3afde4b1468a60ed99c1725e
[8] H. M. Mahmoud, M. D. Ward, Asymptotic distribution of two-protected nodes in random binary
search trees, Appl. Math. Lett. 25(12) (2012) 2218–2222. https://doi.org/10.1016/j.aml.2012.06.005
[9] E. Mohammad Nezhad, M. Javanian, R. Imany Nabiyyi, Weakly protected
nodes in random binary search trees, RAIRO-Theor. Inf. Appl. 56(2) (2022) 1–8.
https://doi.org/https://doi.org/10.1051/ita/2022002
[10] J. Spiess, Some identities involving harmonic numbers, Math. Comput. 55(192) (1990) 839–863.
https://doi.org/10.2307/2008451
[11] L. Yang, S. L. Yang, Weakly protected points in ordered trees, Graphs Combin. 37(3) (2021) 775–
788. https://doi.org/10.1007/s00373-021-02278-w

Volume 10, Issue 4
December 2025
Pages 321-332
  • Receive Date: 09 August 2025
  • Revise Date: 20 August 2025
  • Accept Date: 28 November 2025
  • First Publish Date: 28 November 2025
  • Publish Date: 01 December 2025