Path-minimum queries in trees in O(1) time using O(n) space

Michiel Smid

Let T be a tree with n nodes in which each edge has a real-valued weight. We show how to construct a data structure of size O(n) such that for any two query nodes u and v, the minimum weight of any edge on the path between u and v can be found in O(1) time.