What's wrong with my KD-Tree? (K=2)

Question

More specifically, there's something wrong with my nearest neighbor search. I've confirmed that the tree is built correctly, and that all the helper functions work as expected.

Note this differs slightly from standard KD-trees in that I'm looking for the closest 3 points.

struct Node
{
unsigned int axis;
Point* obj;

struct Node* left;
struct Node* right;
};


void _findClosest(struct Node* current, Point* to, Point** first, Point** second, Point** third, unsigned int depth)
{
if(current == NULL) return;

if(current->left == NULL && current->right == NULL)
{
            //_setOrder updates first, second, and third so that they point to
            //objects that are closest to "to", given an object and the current
            //current first, second, and third.
 _setOrder(to, current->obj, first, second, third);
 return;
}

unsigned int axis = depth % 2;
struct Node* other = NULL;

if(to->getValue(axis) < current->obj->getValue(axis))
{
 other = current->right;
 _findClosest(current->left, to, first, second, third, depth+1);
}
else
{
 other = current->left;
 _findClosest(current->right, to, first, second, third, depth+1);
}

_setOrder(to, current->obj, first, second, third);

if(other == NULL) return;

double searchToBest = _largestDistance(to, *first, *second, *third);
double searchToSplit = _distance(to, current->obj, current->axis);

    //This branch is ALWAYS taken, so this devolves into an O(n) search
if(searchToBest >= searchToSplit)
{
 _findClosest(other, to, first, second, third, depth+1);
}
}

I imagine I'm just misunderstanding the data structure/algorithm in some way.

Minor details:
-if the distance functions are called on NULL objects, they return std::numberic_limits::max()
-this is called on the root of the KD-tree, with a depth of 0, and *first = *second = *third = NULL
-axis = 0 corresponds to X, axis = 1 corresponds to Y

The problem is that every node is visited, rather than seeing the expected reductions from exploiting tree properties. Whatever the flaw is, it makes this a O(n) search.

Answer 1

This line is wrong:

double searchToSplit = _distance(to, current->obj, current->axis);

You want axis, not current->axis. (You're welcome.)