From Wikipedia, KD-Trees:

Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction and hence eliminate the costly step of finding the median at each level of subdivision. [..] This algorithm presorts n points in each of k dimensions

I fail to understand how that is actually done. Consider this example:

Lets say I have 5 points in an array.

0 = (4, 7)
1 = (2, 9)
2 = (5, 4)
3 = (3, 6)
4 = (2, 1) 

I suppose we now want to create 2 sorted arrays, one by X and one by Y ?

Sort them by X     Sort them by Y
1 = (2, 9)         4 = (2, 1) 
4 = (2, 1)         2 = (5, 4)
3 = (3, 6)         3 = (3, 6)
0 = (4, 7)         0 = (4, 7)
2 = (5, 4)         1 = (2, 9)

We start creating the KD-Tree. Lets split by X axis, at the first step. We select the median of the points, 3 = (3, 6), so the Left and right trees will like this:

Left  (first half)         
1 = (2, 9)   
4 = (2, 1)     

Right  (second half)
0 = (4, 7)      
2 = (5, 4)  

Now we want to sort the Left and the Right trees by Y axis. How are we supposed to make use of the points that we sorted previously by Y axis ?

The only solution in my eyes is to re-sort the Left and Right trees respectively, by Y axis. What is Wikipedia talking about ?

  • $\begingroup$ (I hope the sentences following in the wikipedia article sum it up usefully: presorts n points in each of k dimensions using an O(n log n) sort […] prior to building the tree[, maintain] the order of these k presorts during tree construction and thereby [avoid] finding the median at each level of subdivision.) (From skimming the references given, I can't tell the connection to Havran V., Bittner J. "On improving k-d trees for ray shooting" (2002).) $\endgroup$
    – greybeard
    Apr 30, 2016 at 19:37
  • $\begingroup$ Maybe you could try a z-ordering instead of median? Z-ordering (en.wikipedia.org/wiki/Z-order_curve) can be achieved by interleaving the bits of the coordinates. $\endgroup$
    – TilmannZ
    May 2, 2016 at 9:29
  • $\begingroup$ (There is jcgt.org.) $\endgroup$
    – greybeard
    Apr 29, 2020 at 5:23
  • $\begingroup$ Read the paper referred to by Wikipedia ! The sorts are made by means of $k$ indexes, and the points are left in place. Though it is true that the sorts need not be repeated, the cost is $O(n\log n)$, while the medians can be made in O(n) worst-case or expected case. So comparative benchmarking should be made. $\endgroup$
    – user16034
    Apr 19, 2022 at 6:59

1 Answer 1


At depth = 1, with your pre-sorted Y list, you'll still need to perform a comparison to the parent node (and compare by X value).

This ensures that items on the left branch will have X value less than parent node, and items on right branch will have X value greater than parent node.

Since at depth = 1, your list is already pre-sorted by Y value, you save time from sorting at each level.

In the case that your item is the same as the parent node, you don't insert, because that node is already the parent.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.