The left–right-imbalance of binary search trees

AbstractWe present a detailed study of left–right-imbalance measures for random binary search trees under the random permutation model, i.e., where binary search trees are generated by random permutations of {1,2,…,n}. For random binary search trees of size n we study (i) the difference between the left and the right depth of a randomly chosen node, (ii) the difference between the left and the right depth of a specified node j=j(n), and (iii) the difference between the left and the right pathlength, and show for all three imbalance measures limiting distribution results