title: Is constructing a quadtree recursively bad?
body: <p>Consider the following algorithm:</p>
  
  <hr>
  
  <pre><code>Given a list POINTS of length N containing points in the interior of a square, do:
  
  if N=0 or 1, stop
  else, divide the square into 4 subsquares and repeat the above on each subsquare
  </code></pre>
  
  <hr>
  
  <p>Each square is represented by a node, which has associated to it two pieces of information: a list <em>points_contained</em> storing the points of POINTS contained in the square, and a list <em>children</em> pointing to other nodes; thus <em>children</em> is either empty or has 4 elements. The above algorithm thus generates a quadtree in which the external nodes (leafs) represents squares containing at most 1 point of POINTS.</p>
  
  <p>The simplest method of constructing the tree is to follow the above algorithm literally and do recursion on each subsquare (once the 4 subtrees are computed, their roots become children of the original square).So the complexity would satisfy something like C(n)=4*C(n/4) thus be of complexity O(n).</p>
  
  <p>A supposedly smarter method is to start with an empty square (the original square, which is the root node) and add points to it, creating subsquares as necessary: </p>
  
  <pre><code>for each P in POINTS, do: add_point(P,original_square)
  </code></pre>
  
  <p>where we have called the function </p>
  
  <pre><code>add_point(point, square):
    if square.points_contained is empty, add to it P
    is square.children is nonempty:
          find which subsquare s of square contains P then do add_point(P,s)
    if square.children empty: 
    '''*necessarily in this case square is an external node and contains exactly 1 point Q other than P*'''
        continue creating dividing into subsquares until P,Q are no longer contained in the same square
  </code></pre>
  
  <p>The second method is supposedly better than the first, but why? Is it less expensive computationally or memory wise? </p>