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 15Pn/11n.ln n → 1 and 15Wn/14n.ln n→ 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, Transactions on Combinatorics 12 (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, Transactions on Combinatorics 5 (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.
[8] H. M. Mahmoud, M. D. Ward, Asymptotic distribution of two-protected nodes in random binary search trees, Appl. Math. Lett. 25 (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 (2022) 1–8. https://doi.org/https://doi.org/10.1051/ita/2022002
[10] J. Spiess, Some identities involving harmonic numbers, Math. Comput. 55 (1990) 839–863.
https://doi.org/10.2307/2008451
[11] L. Yang, S. L. Yang, Weakly protected points in ordered trees, Graphs Combin. 37 (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