Here is the source of my question.
Given a self-balancing tree (AVL), code a method that returns the median.
(Median: the numerical value separating the higher half of a data sample from the lower half. Example: if the series is
2, 7, 4, 9, 1, 5, 8, 3, 6
then the median is 5.)
I can offer the following solution:
- Traverse the given tree, return the number of elements.
- Traverse
n / 2 + 1
(ifn
is odd) the tree again applying an in-order tree walk. The value of then / 2 + 1
th element is the median.
But I can do it with a binary search tree, can't I? Is there a better algorithm for an AVL?