# Kd-tree in Javascript

I needed to get my head around how kd-trees work, so I coded up a simple implementation that just builds a tree. Naturally, add, delete, balancing etc methods would be required.

See wikipedia: kd-tree

```    /*
* Builds a kd-tree given an array of points
*/
var kdtree = function(points, depth) {
var axis, median, node = {};

if (!points || points.length == 0) return;

// alternate between the axis
axis = depth % points.length;

// sort point array
points.sort((a, b) => a[axis] - b[axis]);

median = Math.floor(points.length / 2);

// build and return node
node.location = points[median];
node.left = kdtree(
points.slice(0, median), depth + 1);
node.right = kdtree(
points.slice(median + 1), depth + 1);
return node;
}```

Example usage would be:

```var points = [ [2,3], [5,4], [4,7], [8,1], [7,2], [9,6] ];
kdtree(points, 0);``` ### oughton

Senior software engineer with extensive experience in enterprise software development targeting wholesale financial organisations and cloud solution providers.

## 4 thoughts on “Kd-tree in Javascript”

1. Chad says:

First where does the buildTree() function come from. I can’t seem to run this without this function throwing a error.

Secondly, what does depth refer to? As in what should be supplying for that function argument?

Finally, if I had a array of objects with a set of coordinates in it how would I process them so that the rest of the function works as is? points.pos[‘x’] for example

1. oughton says:

First where does the buildTree() function come from. I can’t seem to run this without this function throwing a error.
This was a copy and paste / re-factor error. It should be ‘kdtree’ not ‘buildTree’. I have updated this in the post now. Thanks for that.

Secondly, what does depth refer to? As in what should be supplying for that function argument?
Depth is the tree depth, so pass it 0 to begin with. Alternatively you could check if there is a second parameter passed into the function and if not then set depth to be 0.
Finally, if I had a array of objects with a set of coordinates in it how would I process them so that the rest of the function works as is? points.pos[‘x’] for example
You could just pre process these point objects before passing them to the function. eg:

``` var points = [ { pos: { x: 1, y: 2 } }, { pos: { x: 5, y: 1 } }, { pos: { x: 3, y: 2 } } ]; var flat = []; for (var i in points) { var point = points[i].pos; flat.push([ point.x, point.y ]); }```

``` ```

```kdtree(flat, 0); ```

2. madeinquant says:

1. oughton says: