title: Trees: Linked Lists vs Arrays (Efficiency)
body: <p>This is an assignment question that I am having trouble wording an answer to.</p>
  
  <p>"Suppose a tree may have up to k children per node. Let v be the average number of children per node. For what value(s) of v is it more efficient (in terms of space used) to store the child nodes in a linked list versus storage in an array? Why?"</p>
  
  <p>I believe I can answer the "why?" more or less in plain English -- it will be more efficient to use the linked list because rather than having a bunch of empty nodes (ie empty indexes in the array if your average is lower than the max) taking up memory you only alloc space for a node in a linked list when you're actually filling in a value. </p>
  
  <p>So if you've got an average of 6 children when your maximum is 200, the array will be creating space for all 200 children of each node when the tree is created, but the linked list will only alloc space for the nodes as needed.  So, with the linked list, space used will be approximately(?) the average; with the array, spaced used will be the max.</p>
  
  <p>...I don't see when it would ever be more efficient to use the array.  Is this a trick question?  Do I have to take into account the fact that the array needs to have a limit on total number of nodes when it's created?</p>