title: Nasty bug in build-routine of a KD-Tree
body: <p>I'm currently trying to build a KD-Tree in 2 dimensions (Latitude and Longitude) to query for the nearest coordinate. I push the coordinates (ID, Latitude, Longitude) in a vector and pass this vector in the constructor of my KD-Tree.</p>
  
  <p>But when I set a breakpoint to the end of the constructor (after the recursive build-call returned) <strong>my root-item contains just rubbish in its left- and right-pointers</strong>. During the build-routine it seems that they contain quite a long time the right values, but at some point they get lost... does anyone see the mistake i obviously made in my recursive routine?</p>
  
  <pre><code>#include "stdafx.h"
  #include "KDTree.h"
  
  
  KDTree::KDTree(void)
  {
  }
  
  KDTree::KDTree(vector&lt;Coordinate*&gt; c)
  {
      coordinates = c;
      root = &amp;KDItem();
      build(root, 0, 0, c.size() - 1);
  }
  
  
  KDTree::~KDTree(void)
  {
  }
  
  void KDTree::build(KDItem* item, int depth, int startIndex, int stopIndex)
  {
      int coordinateCount = stopIndex - startIndex + 1;
      if (coordinateCount == 1)
      {
          (*item).left = NULL;
          (*item).right = NULL;
          (*item).value = NULL;
          (*item).leaf = coordinates[startIndex];
          return;
      }
  
      (*item).left = &amp;KDItem();
      (*item).right = &amp;KDItem();
  
      int medianIndex = 0;
      float median = 0;
  
      if (depth % 2 == 0)
      {
          sort(coordinates.begin() + startIndex, coordinates.begin() + stopIndex + 1, Coordinate::sortByLatitude);
          Coordinate::findLatitudeMedian(&amp;coordinates, startIndex, stopIndex, &amp;median, &amp;medianIndex);
      }
      else
      {
          sort(coordinates.begin() + startIndex, coordinates.begin() + stopIndex + 1, Coordinate::sortByLongitude);
          Coordinate::findLongitudeMedian(&amp;coordinates, startIndex, stopIndex, &amp;median, &amp;medianIndex);
      }
  
      (*item).value = median;
      build((*item).left, depth+1,startIndex, medianIndex-1);
      build((*item).right, depth+1,medianIndex,stopIndex);
  }
  
  int KDTree::findNearestNodeIndex(float latitude, float longitude)
  {
      KDItem* item = findNearestItem(latitude, longitude, root);
      return (*(*item).leaf).Index();
  }
  
  KDItem* KDTree::findNearestItem(float firstVal, float secondVal, KDItem* item)
  {
      if ((*item).value == NULL) return item;
  
      if (firstVal &lt; (*item).value)
      {
          return findNearestItem(secondVal, firstVal, (*item).left);
      }
      else
      {
          return findNearestItem(secondVal, firstVal, (*item).right);
      }
  }
  </code></pre>