An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, i.e. a metric is a tree metric iff every 4 point subspace is a tree metric. In particular this implies that one can decide in polynomial time whether a given metric is a tree metric by examining all quadruples of points in the space.
My question now is what other (than the trivial) algorithms are there? Can one check in linear (in the number of points) time whether a metric is a tree metric?