Implementation of k-d-Tree

I am a complete beginner in C and I have started learning it by implementing binary trees. So have implemented a basic k-d-Tree. I provide two structs and two methods for comparing values on different axis.

typedef struct Point2D {
    double x;
    double y;
} Point2D;

int x_comparator(const void *v1, const void *v2) {
    const Point2D *p1 = (Point2D *) v1;
    const Point2D *p2 = (Point2D *) v2;
    if (p1->x x)
        return -1;
    else if (p1->x > p2->x)
        return +1;
    else
        return 0;
}

int y_comparator(const void *v1, const void *v2) {
    const Point2D *p1 = (Point2D *) v1;
    const Point2D *p2 = (Point2D *) v2;
    if (p1->y y)
        return -1;
    else if (p1->y > p2->y)
        return +1;
    else
        return 0;
}

#define DIMENSION 2

typedef struct KdNode {
    Point2D *p;
    struct KdNode *left, *right;
    int splittingAxis;
} KdNode;

and my method for building the k-d-Tree :

```
KdNode* build(Point2D data[], int splittingAxis, int numberElements) {
KdNode temp = (KdNode) malloc(sizeof(KdNode));
KdNode left = (KdNode) malloc(sizeof(KdNode));
KdNode right = (KdNode) malloc(sizeof(KdNode));
if (temp == NULL || left == NULL || right == NULL) {
exit(1);
}
if (numberElements == 0) {
return NULL;
}

int median, numberElementsLeft, numberElementsRight;
median = floor(numberElements / 2);
Point2D leftSide[median], rightSide[numberElements - median - 1];
splittingAxis = splittingAxis % DIMENSION;

if (splittingAxis == 0) {
qsort(data, numberElements, sizeof(Point2D), x_comparator);
} else {
qsort(data, numberElements, sizeof(Point2D), y_comparator);
}

numberElementsLeft = median;
numberElementsRight = numberElements - median - 1;

memcpy(leftSide, data, numberElementsLeft * sizeof(Point2D));
memcpy(rightSide, &data[numberElements - median],
numberElementsRight * sizeof(Point2D));

Point2D *tPoint = (Poin

malloc

You should not cast the return value from malloc() in C. Instead, include its header file, and let the compiler's conversion from void* to specific pointer happen naturally.:

KdNode *temp = malloc(sizeof (KdNode));

It's often better to use the size of the actual object(s) you're allocating, rather than the size of the type. This isn't an issue here, where your declaration is on the same line as the allocation, but consider this:

temp = malloc(sizeof (KdNode));

If you can't see the declaration, then it's harder to be sure that sizeof KdNode is the right size. Instead we can write:

temp = malloc(sizeof *temp);

This also eliminates some irritating parentheses, which is nice!
error behaviour

What should happen when you misuse the function? Here, you have two different behaviours:

if (temp == NULL || left == NULL || right == NULL) {
    exit(1);
}
if (numberElements == 0) {
    return NULL;
}

If anything, these are the wrong way around - you abort the whole program for an unpredictable run-time failure from malloc(), but nicely return a null value when you're (avoidably) given nonsense arguments. It's generally best not to invoke exit() from a function you want anybody to be able to use anywhere; I'd make both cases return NULL. And change the test for numberElements to be <= 0, or its type to unsigned.
comparators

Comparators for qsort can return any positive value or any negative value or zero as results. So they don't need to be coerced to -1/0/+1; however, as you've noticed, the difference may be out of range for an int. However, there's an easier way to obtain a value of correct sign, and the default conversion will work for us:

#include 
int x_comparator(const void *v1, const void *v2) {
    const Point2D *p1 = v1;
    const Point2D *p2 = v2;
    return copysign(1, p1->x - p2->x);
}

I took out the unnecessary casts from void* here, too.
avoid floor() with integer division

This has an unnecessary round-trip through floating-point and back:

median = floor(numberElements / 2);

Integer division rounds down, so numberElements / 2 is sufficient.
possible simplification of if/else

Most of this is invariant between the two branches:

if (splittingAxis == 0) {
    qsort(data, numberElements, sizeof(Point2D), x_comparator);
} else {
    qsort(data, numberElements, sizeof(Point2D), y_comparator);
}

You might choose to make only the comparator argument dependent on the condition:

qsort(data, numberElements, sizeof *data, splittingAxis ? y_comparator : x_comparator);

If that's too opaque, then you could define a variable:

int (*const comparator)(const void*, const void*)
    = splittingAxis ? y_comparator : x_comparator;

qsort(data, numberElements, sizeof *data, comparator);

In honesty, the original may well be the best option here (but using sizeof *data rather than sizeof (Point2D) helps ensure a type match).

One approach that works well is to use splittingAxis to index an array. To me, this looks compact and clear :

/* qsort-compatible comparator functions */
typedef int Comparator(const void*, const void*);
Comparator *const comparators[] = {x_comparator, y_comparator };

qsort(data, numberElements, sizeof *data, comparators[splittingAxis]);

copy whole struct

Here you copy a Point2D member-by-member:

tPoint->x = data[median].x;
tPoint->y = data[median].y;

We can write that as:

*tPoint = data[median];

always check allocators' return value before use

You got this right early in the function, but tPoint is accessed immediately after allocation with no check it isn't null.

Modified version:

I've reordered some code and eliminated some local variables to give something that reads better to me. See whether you agree.

```
#include
#include
#include

typedef struct Point2D {
double x;
double y;
} Point2D;

static int x_comparator(const void v1, const void v2) {
const Point2D *p1 = v1;
const Point2D *p2 = v2;
return copysign(1, p1->x - p2->x);
}

static int y_comparator(const void v1, const void v2) {
const Point2D *p1 = v1;
const Point2D *p2 = v2;
return copysign(1, p1->y - p2->y);
}

typedef struct KdNode {
Point2D *p;
struct KdNode left, right;
int splittingAxis;
} KdNode;

/ qsort-compatible comparator functions /
typedef int Comparator(const void, const void);
Comparator *const comparators[] = {x_comparator, y_comparator };

KdNode* build(Point2D data[],
unsigned int splittingAxis,
unsigned int numberElements)
{
if (numberElements 1) {
return NULL;
}

KdNode temp = malloc(sizeof temp);
KdNode left = malloc(sizeof left);
KdNode right = malloc(sizeof right);
if (!temp || !left || !right) {
return NULL;
}

temp->p = malloc(sizeof *temp->p);
if (!temp->p) {
return NULL;
}

StackExchange Code Review Q#158486, answer score: 6