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.
Kazemi, R. and Zamani Mehreyan, S. (2025). Path length of protected nodes in random binary search trees. Journal of Discrete Mathematics and Its Applications, 10(4), 321-332. doi: 10.22061/jdma.2025.12370.1151
MLA
Kazemi, R. , and Zamani Mehreyan, S. . "Path length of protected nodes in random binary search trees", Journal of Discrete Mathematics and Its Applications, 10, 4, 2025, 321-332. doi: 10.22061/jdma.2025.12370.1151
HARVARD
Kazemi, R., Zamani Mehreyan, S. (2025). 'Path length of protected nodes in random binary search trees', Journal of Discrete Mathematics and Its Applications, 10(4), pp. 321-332. doi: 10.22061/jdma.2025.12370.1151
CHICAGO
R. Kazemi and S. Zamani Mehreyan, "Path length of protected nodes in random binary search trees," Journal of Discrete Mathematics and Its Applications, 10 4 (2025): 321-332, doi: 10.22061/jdma.2025.12370.1151
VANCOUVER
Kazemi, R., Zamani Mehreyan, S. Path length of protected nodes in random binary search trees. Journal of Discrete Mathematics and Its Applications, 2025; 10(4): 321-332. doi: 10.22061/jdma.2025.12370.1151
)
)