The Expected Distribution of Degrees in Random Binary Search Trees
Hosam M. Mahmoud · The Computer Journal · 1986
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.