As mentioned Bober02's answer, a k-d tree may be built by partitioning via either a presorting algorithm or a median of medians algorithm. These two algorithms are discussed in detail in the following two publications.

https://www.jcgt.org/published/0004/01/03/

https://arxiv.org/abs/1410.5420

Both publications provide source code for implementations of the tree-building algorithms; however, the arXiv publication provides highly optimized implementations relative to the Journal of Computer Graphics Techniques publication.