title: How to construct an octree in C++
body: <p>I am implementing an Octree in C++ which should later contain a mesh for rendering. But at the moment I am struggeling with the construction of the Octree. To be more precisely it is the addNode() function which causes problems. I thought of a recursive implementation similar to a binary tree:
  <a href="https://stackoverflow.com/questions/20444612/binary-tree-implementation-c">Binary Tree implementation C++</a></p>
  
  <p>However, in an octree every node has 8 sons and not only 2. Furthermore, therefore I cannot use a simple switch (left/right) as in the binary tree to decide where to add the node. I would need to check if one of the 8 sons is empty (pointer is NULL) and if no pointer is null I would need to call the add function with one of the sons as an argument. However, this will result in an octree where always the first son will contain all following sub octrees. How is this add function commonly implemented and this problem avoided? </p>