If you have an avl tree, whats the best way to get the median from it? The median would be defined as the element with index ceil(n/2) (index starts with 1) in the sorted list.

So if the list was 1 3 5 7 8

median is 5

if the list was 1 3 5 7 8 10

median is 5

Assume you can augment the tree. In this case, I think it's best to let each node know the size (number of nodes) of the subtree, (i.e. 1+left.size+right.size)

But using this, the best way I can think of makes median searching O(lg n) time because you can traverse by comparing indexes. Is there a better way?