Neat use of these is the "fast multipole method" for stimulating galaxies.

If you want to compute the gravitational force on a given star exactly you need to figure out the forces from all other stars and add them up. This will be n^2 and slow. But turns out you can get a good approximation by dividing up space with a kd tree and using the average force from each cell to represent the stars underneath it in the tree. This gets you to nlogn

https://en.m.wikipedia.org/wiki/Fast_multipole_method