${\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}****$

Finds and retrieves the median data of the passed in AVL.

This can be done in $O(n)$ time. That being said, this method will not need

to traverse the entire tree to function properly, so you should only

traverse enough branches of the tree necessary to find the median data

and only do so once. Failure to do so will result in an efficiency penalty.

Ex: $$

Given the following AVL composed of Integers

$\backslash$table$[[*,,,,10,,],[*,,,1,,1,1],[*,,25,,,,75],[*,,1,1,,,11],[*,,13,37,70,,80],[*,1,1,1,,,1],[*,12,15,,40,,85]]$

findMedian$()$ should return $40$

@ithrows java. util. NoSUchElementException if the tree is empty or contains an even number o$.$

@return the median data of the AVL

$**1$

$2$ usages

public $T$ findMedian$()\{$