Incorrect heuristic in distanceRecurse()

[ab3nd]

The distanceRecurse() function uses a heuristic of checking if the difference between the current node's left point and the key being retrieved in the next dimension is greater than the dimension specified by the user, and if so, it skips the left tree rather than recursing it. Similarly, it checks the difference between the key and the current node's right point in the current dimension, and if it is greater than the desired dimension, skips it.

To see why this is wrong, imagine that the nodes are spread out in the space x=[-5, 5] y = [-5, 5]. The first (root) node is inserted at (4,4). Then a bunch of other nodes are inserted, including ones that are arbitrarily close to the root. Then the user calls distanceNeighbors to get all neighbors within in a distance of 1 from the point (-2, -1). Looking at the root's left, we see that the difference is abs(-1 - some value arbitrarily close to 4), so about 5. 5 is more than 1, so we skip the left tree. Looking at the root's right, the same thing happens, so we also skip the right tree and don't find any nodes.

Removing the distance heuristic fixes this, at the cost of searching the entire tree to find the nodes within a fixed distance of a given point.