An O(nlogn) version of the Averbakh-Berman algorithm for the robust median of a tree

We show that the minmax regret median of a tree can be found in O(nlogn) time. This is obtained by a modification of Averbakh and Berman's O(nlog2n)-time algorithm: we design a dynamic solution to their bottleneck subproblem of finding the middle of every root-leaf path in a tree.