Profiles of random trees: correlation and width of random recursive trees and binary search trees
Profiles of random trees: correlation and width of random recursive trees and binary search trees
In a tree, a level consists of all those nodes that are the same distance from the root. We derive asymptotic approximations to the correlation coefficients of two level sizes in random recursive trees and binary search trees. These coefficients undergo sharp sign-changes when one level is fixed and the …