The shortest distance _is_ still a straight line, it's just not a cartesian line. Hamming distance (which is what the entire article is about and somehow doesn

The shortest distance _is_ still a straight line, it's just not a cartesian line. Hamming distance (which is what the entire article is about and somehow doesn't mention it, or edit distance, or anything along those lines) is still a metric space, and still follows all the standard triangle inequality properties. If you convert your standard tree into a BK tree, suddenly all the assumptions about tree structures come back.