title: Are Linear Quadtrees the most efficient way to store grid division data
body: <p>Let's say you have a 32x32 grid that could be randomly subdivided using any of the block sizes below:</p>
  
  <p>32x32, 16x16, 8x8, 4x4</p>
  
  <p>How many times the grid is subdivided and in what way the subdivisions happen is determined at random. </p>
  
  <p>Visually it could look something like this:</p>
  
  <p><a href="https://i.stack.imgur.com/x643l.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/x643l.png" alt="enter image description here"></a></p>
  
  <p>This type of data can be represented using a <a href="https://en.wikipedia.org/wiki/Quadtree" rel="nofollow noreferrer">quad tree</a>. </p>
  
  <p><strong>My question is:</strong></p>
  
  <p>If I was trying to use the least amount of bytes possible to represent the graph above, would a Linear Quad-tree be the most efficient way of doing this?</p>
  
  <p>The only other alternative I could think of would be to make all the possible combinations of the graph, and use a single number to represent each combination.</p>
  
  <p>So for the graph there are 4 levels of branching (32x32, 16x16, 8x8, 4x4) this would give us 4^0 + 4^1 + 4^2 + 4^3 possible combinations which is equal to 85 combinations. </p>
  
  <p>Therefore the smallest way I can think of to store the graph would be to use 7 bits (1010101 is the number 85 in binary) to represent the possible combinations.</p>
  
  <p>Would <a href="http://www.csee.usf.edu/~tuy/Literature/QTree-Represent-CACM82.pdf" rel="nofollow noreferrer">Linear Quadtrees</a> equal this in terms of storage efficiency, or would they take up more or less space?</p>