title: K-d trees: nearest neighbor search algorithm
body: <p>This is my understanding of it:
  1. Recurse down the tree, taking the left or right subtree according as whether ELEMENT would lie in the left or the right subtree, if it existed.
  2. Set CURRENT_BEST as the first leaf node that you reach.
  3. As you recurse back up, check to see whether ELEMENT lies closer to the splitting hyperplane than it does to CURRENT_BEST. If so, set CURRENT_BEST as the current node.</p>
  
  <p>This is the part I got from <a href="https://en.wikipedia.org/wiki/K-d_tree" rel="nofollow">Wikipedia</a> and my class, and the part I don't understand:
  4. Check to see whether any node in the other subtree of the splitting point singled out in 3. is closer to ELEMENT than the splitting point.</p>
  
  <p>I don't see why we need to do 4., since any point that might lie in the one subtree of the splitting node must necessarily be closer to the splitting node than to any point in the other subtree.</p>
  
  <p>It's obviously my understanding of the algorithm that is flawed, so help will be greatly appreciated.</p>