Let Vi be the set of vertices of degree, i, i=1,2,3, in a random binary search tree. We prove that E(|Vi|)=n∣3+0(1), for i=1,2,3. This result tells us that the expected tree shape does not contain very long path subgraphs; thus in a sense the expected shape tends to be balanced.
No takes yet. Share an insight, caveat, or question.
Hosam M. Mahmoud (1986) studied this question.