title: BFS to DFS octree conversion in python
body: <p>I'm working with an octree that has been built by third party software. This software reports how to traverse the tree in a breadth first manner, but I want to traverse the tree in a depth first manner. </p>
  
  <p>For my application (building a grid out of particle data for astrophysics applications) I tend to think of octrees in terms of their 'refined' lists, i.e. for a cell that doesn't refine, we would have:</p>
  
  <pre><code>False
  </code></pre>
  
  <p>Whereas for a single cell that refines into an Oct, we would have:</p>
  
  <pre><code>True
  False
  False
  False
  False
  False
  False
  False
  False
  </code></pre>
  
  <p>My goal is to convert such a <code>refined</code> list that is generated in a Breadth First manner into a Depth First manner (in python), but am at a loss as to where to start.  </p>
  
  <p>For an example this code:</p>
  
  <pre><code>def construct_octree(refined=[True]):
  
      # Loop over subcells
      for subcell in range(8):
  
          # Insert criterion for whether cell should be sub-divided. Here we
          # just use a random number to demonstrate.
          divide = random.random() &lt; 0.5
  
          # Append boolean to overall list
          refined.append(divide)
  
          # If the cell is sub-divided, recursively divide it further
          if divide:
              construct_octree(refined)
  
      return refined
  
  oct = construct_octree()
  </code></pre>
  
  <p>would create the <code>refined</code> list for a depth first traversal.  </p>