 <p>Pretty late on answering this question. Guess I had never worked on this problem then. But not that I have been looking into it for sometime now, I can share some insight. What @greedybuddha is saying is mostly right, but they are tricks and techniques to prevent creating the tree entirely every time step. As usual these techniques with their own overheads (memory footprint etc) and necessary trade-offs need to be made. Also, it may not be possible to apply them in all situations. </p> <ol> <li><p><strong>Allocate enough memory upfront to handle octree of a given depth. Deallocate the memory only when all timessteps have finished.</strong> For example suppose for all n-body input data sets you are going to use, you know that your Octree will never go beyond a depth of say 10. In that case it is easy to figure out how many maximum nodes you octree might have(usually its a geometric progression sum). By doing a bit of bookkeeping(valid child indexes of each node) for every octree node, it is easy to reuse this buffer to fill in octree nodes without needing to allocate/deallocate octree nodes every timestep. Clearly the likely overhead here is that you might be wasting lot of memory but then you gain performance by not doing allocation/deallocation every timestep Usual way of going about bounding the number of octree levels is to allow multiple bodies per leaf node (last level of octree or smallest cell size of octree grid)</p></li> <li><p><strong>Create a new Octree only when needed</strong>: It is possible to think about a situation where octree doesn't change for some series (burst) of timesteps and then it changes and the pattern repeats. This can happen only when bodies positions change insignificantly over a timestep burst such that octree structure remains the same during that burst. And in what situation will bodies move slowly - when the chosen timestep size is pretty small, forces exerted + initial momentum on bodies is small. How to dynamically figure out such bursts is a difficult problem. This is a more tricky technique and I dont know whats the easy way to do this. This requires some insight of timestep granularity, initial velocity/acceleration of the bodies and kind of forces the bodies are dealing with.</p></li> </ol>