title: How to get all parents for all leaves in a tree quickly?
body: <p>I have a possibly large rooted tree structure that I want to transform into a <code>X * Y</code> matrix with <code>X</code> being the amount of leaves in the tree and <code>Y</code> being the amount of nodes in the tree with a degree larger than 1, i.e. the root node and internal nodes. The matrix should be filled as such:</p>
  
  <p>M<sub>i,j</sub> = { <code>0</code> if leaf <code>i</code> has ancestor <code>j</code>, 1 otherwise</p>
  
  <p>For example, this tree:</p>
  
  <pre><code>      --A 
       /
      1   B
     / \ /
    /   3  
   /     \
  0       C
   \ 
    \   --D
     \ /
      2
       \--E
  </code></pre>
  
  <p>would translate into this matrix:</p>
  
  <pre><code>  0 1 2 3
  A T T F F
  B T T F T
  C T T F T
  D T F T F
  E T F T F
  </code></pre>
  
  <p>Since the trees might become pretty big (possibly ~100,000 leaves), I was wondering if there is a smarter/faster way of doing this than traversing up the tree for every one of the leaf nodes. It feels like some kind of algorithm is in this problem somewhere, but I haven't figured it out yet. Maybe someone can help?</p>
  
  <p>In my application, the tree represents large <a href="http://arthropoda.files.wordpress.com/2010/02/arthrophyloregier2010.jpg" rel="nofollow">phylogenetic hierarchies</a>, so it is not balanced and there might be nodes with more than two children.</p>