Lower estimate:-
Find a lower bound Pl (n) for the average path length of a BST, and show that this average length is in fact ( log n).(Balanced)
Consider a binary tree balanced as much as possible. Suppose that all elements at the bottom level are first considered for exchange upward, then the next level, etc.
However, a child is bubbled up only if its key value is less than that of its parent and no greater than that of its sibling. Show that once an element bubbles upward (after processing its entire level), it never moves down again. Hence, argue that putting an n-node tree in partial order with the bubble up process is an O(n log n) process.