Implementation of K-DTrees (2-D)

/*
    * If all points are in k – dimensions then Select one of the dimension for a level.
    * Get median element in selected dimension.
    * Push all points smaller than median elements in left sub tree and all greater points in right sub tree.
    * Recursively call the buildTree function with leftSubset and Set leftChild of curNode.
    * Recursively call the buildTree function with rightSubset and set rightChild of curNode.
*/

#include <iostream>
#include <vector>

using namespace std;

class Point
{
public:
       int x;
       int y;
     
       Point()
       {
           x = 0;
           y = 0;
       }
     
       Point(int xp, int yp)
       {
           x = xp;
           y = yp;
       }
};

class TreeNode
{
public:
      Point p;
      TreeNode *left;
      TreeNode *right;
         
      TreeNode()
      {
         left = NULL;
         right = NULL;
      }
   
      TreeNode(Point pt)
      {
          p = pt;
          left = NULL;
          right = NULL;
      }
};

class KDTree
{
      TreeNode *root;
public:
      KDTree()
      {
           root = NULL;
      }
   
      TreeNode* getRoot()
      {      
          return root;
      }
   
      TreeNode* createNode(Point ptr)
      {
           TreeNode *n = new TreeNode(ptr);
           return n;
      }
   
      void CreateLeftRightSubset(vector <Point> PointSet, Point median, vector <Point> &leftSet, vector <Point> &rightSet, int depth)
      {
           // Check x coordinates
           if(depth %2 == 0)
           {
                // Push all points having x coordinate
                // less than median to leftSet and rest to right set
                for(int i=0; i < PointSet.size() ; i++)
                {
                     // Skip median.
                     if(PointSet[i].x == median.x && PointSet[i].y == median.y )
                         continue;
                     if(PointSet[i].x < median.x)
                         leftSet.push_back(PointSet[i]);
                     else
                         rightSet.push_back(PointSet[i]);
                }
           }
           // Check y coordinates
           else
           {
                // Push all points having y coordinate
                // less than median to leftSet and rest to rightSet.
                for(int i=0; i < PointSet.size() ; i++)
                {
                     // Skip median.
                     if(PointSet[i].x == median.x && PointSet[i].y == median.y )
                         continue;
                     if(PointSet[i].y < median.y)
                         leftSet.push_back(PointSet[i]);
                     else
                         rightSet.push_back(PointSet[i]);
                }
           }
      }
   
      // Sort vector on x coordinates
      void sortX(vector <Point> &PointSet);

      // Sort vector on y coordinates
      void sortY(vector <Point> &PointSet);
   
      // Return median of all points in PointSet.
      Point getMedian(vector <Point> &PointSet , int depth)
      {
            //Median of x coordinates.
            if(depth % 2 ==0 )
            {
                sortX(PointSet);
                Point M = PointSet[PointSet.size()/2];
                // To prevent infinite recurrence
                if(M.x > PointSet[0].x)
                {
                    return M;
                }
                M.x = M.x+1;
                return M;
            }
            //Median of y coordinates.
            else
            {
                sortY(PointSet);
                Point M = PointSet[PointSet.size()/2];
                // TO prevent infinite recurrence
                if(M.y > PointSet[0].y)
                {
                     return M;
                }
                M.y = M.y+1;
                return M;
            }
      }
   
      TreeNode* buildTree(vector <Point> PointSet , int depth)
      {
           if(PointSet.size() == 1)
               return (createNode(PointSet[0]));

           Point M = getMedian(PointSet,depth);
           TreeNode* curNode = createNode(M);
           if(isEmpty())
                root = curNode;
           vector <Point> leftSet;
           vector <Point> rightSet;
         
           CreateLeftRightSubset(PointSet,M,leftSet,rightSet,depth);
           if(leftSet.size() != 0)
                      curNode->left = buildTree(leftSet, depth+1);
           if(rightSet.size() != 0)
                      curNode->right = buildTree(rightSet, depth+1);
           return curNode;
      }
   
};

int main()
{
    vector <Point> v;
    v.push_back(Point(6,1));
    v.push_back(Point(5,5));
    v.push_back(Point(9,6));
    v.push_back(Point(3,6));
    v.push_back(Point(4,9));
    v.push_back(Point(4,0));
    v.push_back(Point(7,9));
    v.push_back(Point(2,9));
    KDTree tree;
    tree.buildTree(v,0);
    tree.preorder(tree.getRoot());
    system("pause");
}